Java 數(shù)據(jù)結(jié)構(gòu)進(jìn)階二叉樹題集上
二叉樹操作的代碼大多數(shù)使用遞歸來實(shí)現(xiàn)，代碼會(huì)比較簡潔，如果使用非遞歸，代碼會(huì)比較的繁榮，而且不易理解。（上）中的題偏向于基礎(chǔ)，后面（下）中的題機(jī)會(huì)比較難。
1、二叉樹的遍歷
（1）前、中、后序遍歷
這里寫到的遍歷是遞歸遍歷，代碼比較簡單，后續(xù)會(huì)寫非遞歸的代碼。以前序遍歷為例：
如果根節(jié)點(diǎn)root為空，直接返回，否則，打印根節(jié)點(diǎn)，再分別遞歸root的左子樹和右子樹即可。中序遍歷的話，先中序遍歷左子樹，打印根節(jié)點(diǎn)，再中序遍歷右子樹即可。
【代碼如下】
//遞歸實(shí)現(xiàn)，比較簡單
public void preTree(Node root){
if(root==null){
return;
}
System.out.print(root.val+" ");
preTree(root.left);
preTree(root.right);
}（2）層序遍歷
OJ的返回值為一個(gè)存放鏈表的鏈表，所以我們可以將每一層的元素存放在同一個(gè)鏈表中，作為元素存放在要返回的鏈表中。還是使用隊(duì)列來遍歷鏈表，每次出根節(jié)點(diǎn)，當(dāng)其左右節(jié)點(diǎn)不為空的時(shí)候，入左右節(jié)點(diǎn)。直到隊(duì)列為空，遍歷完成。
如何判斷二叉樹每層結(jié)點(diǎn)的個(gè)數(shù)？
在對每層節(jié)點(diǎn)出隊(duì)完成后，隊(duì)列中剩余結(jié)點(diǎn)的個(gè)數(shù)就是下一層結(jié)點(diǎn)的個(gè)數(shù)。比如：現(xiàn)在給隊(duì)列如跟節(jié)點(diǎn)，隊(duì)列大小為1，第一層的節(jié)點(diǎn)個(gè)數(shù)就為1；當(dāng)根節(jié)點(diǎn)出對后，我們需要入隊(duì)根節(jié)點(diǎn)的左右節(jié)點(diǎn)，如果左節(jié)點(diǎn)為null，則只入右節(jié)點(diǎn)，此時(shí)隊(duì)列大小為1，第二層的節(jié)點(diǎn)個(gè)數(shù)就為1。
【代碼如下】
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret=new ArrayList<>();
if(root==null){
return ret;
}
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> list=new ArrayList<>();
int size=queue.size();
while(size--!=0){
TreeNode node=queue.poll();
list.add(node.val);
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
}
ret.add(list);
}
return ret;
}2、獲取樹中子結(jié)點(diǎn)的個(gè)數(shù)
通常二叉樹的問題，都會(huì)有兩種思路：遍歷思路和子問題思路。
如這道題：
我們可以求出它的左子樹和右子樹中子結(jié)點(diǎn)的個(gè)數(shù)，相加即可；或者，定義計(jì)數(shù)器，因?yàn)橐f歸，所以我們需要一個(gè)全局變量（count），遞歸左右子樹，只要遇到子節(jié)點(diǎn)，count就加一。
【代碼如下】
//獲取葉子節(jié)點(diǎn)的個(gè)數(shù)
//方法一
public int getLeafNodeCount1(Node root){
if(root==null){
return 0;
}
if(root.left==null&&root.right==null){
return 1;
}
return getLeafNodeCount1(root.left)+getLeafNodeCount1(root.right);
}
// 方法二
public static int count1;
public void getLeafNodeCount2(Node root){
if(root==null){
return ;
}
if(root.left==null&&root.right==null){
count1++;
}
getLeafNodeCount2(root.left);
getLeafNodeCount2(root.right);
}3、獲取二叉樹的高度
獲取二叉樹的高度，我們只需要獲取二叉樹左右子樹的高度，返回左右子樹的最大高度加一即可。
【代碼如下】
// 獲取二叉樹的高度
public int getHeight(Node root){
if(root==null){
return 0;
}
int left=getHeight(root.left);
int right=getHeight(root.right);
return left>right?left+1:right+1;
}4、判斷是不是完全二叉樹
【完全二叉樹和滿二叉樹】
- 滿二叉樹: 一棵二叉樹，如果每層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這棵二叉樹就是滿二叉樹。也就是說，如果一棵二叉樹的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是 2^K-1，則它就是滿二叉樹。
- 完全二叉樹: 完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號從0至n-1的結(jié)點(diǎn)一一對應(yīng)時(shí)稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。
判斷完全二叉樹，我們可以借助隊(duì)列來實(shí)現(xiàn)，在二叉樹不為空的情況下，對二叉樹進(jìn)行層序遍歷：定義一個(gè)隊(duì)列，將根節(jié)點(diǎn)放入，只要隊(duì)列不為空，進(jìn)行出隊(duì)，將得到的節(jié)點(diǎn)的左右節(jié)點(diǎn)入隊(duì)，注意先左后右，節(jié)點(diǎn)為空也要進(jìn)行入隊(duì)（隊(duì)列可以存儲(chǔ)null）。直到遇到第一個(gè)出隊(duì)的節(jié)點(diǎn)為null，對隊(duì)列中剩下的元素進(jìn)行遍歷，如果全為null，則為完全二叉樹；如果存在不為null的結(jié)點(diǎn)，則不是完全二叉樹。
public boolean isCompleteTree(Node root){
Queue<Node> queue=new LinkedList<>();
queue.offer(root);
//如果隊(duì)列為空，會(huì)存在空指針異常
while(!queue.isEmpty()){
//層序遍歷
Node node=queue.poll();
if(node!=null){
//將節(jié)點(diǎn)的左右子節(jié)點(diǎn)放入隊(duì)列
queue.offer(node.left);
queue.offer(node.right);
}else{
//如果node為null，直接對隊(duì)列進(jìn)行判斷
break;
}
}
int x=queue.size();
//判斷隊(duì)列元素是否全為null
for(int i=0;i<x;++i){
if(queue.poll()!=null){
return false;
}
}
return true;
}5、判斷兩個(gè)樹是否相同
存在以下四種情況：
【代碼如下】
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null&&q!=null||p!=null&&q==null){
return false;
}
if(p==null&&q==null){
return true;
}
if(p.val!=q.val){
return false;
}
return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
}
}6、另一棵樹的子樹
上面已經(jīng)給寫過判斷兩棵樹是否相等的題，我們只需要判斷樹p是否等于樹q，或者數(shù)p的左子樹或右子樹是否等于樹q。分為以下幾種情況：
【代碼如下】
class Solution {
//判斷兩個(gè)樹是否相等
public boolean isSameTree(TreeNode root,TreeNode subRoot){
if(root==null&&subRoot!=null||root!=null&&subRoot==null){
return false;
}
if(root==null&&subRoot==null){
return true;
}
if(root.val!=subRoot.val){
return false;
}
return isSameTree(root.left,subRoot.left)&&isSameTree(root.right,subRoot.right);
}
//判斷子樹
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(root==null||subRoot==null){
return false;
}
if(isSameTree(root,subRoot)){
return true;
}
return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);
}
}7、判斷平衡二叉樹
高度平衡二叉樹定義為：
一個(gè)二叉樹每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹的高度差的絕對值不超過 1 。
首先我們需要寫一個(gè)函數(shù)來求二叉樹的高度，只要這個(gè)二叉樹的左右子樹高度差不大于1，且左右子樹都是平衡二叉樹，則其為平衡二叉樹。
【代碼如下】
class Solution {
//求二叉樹的高度
public int maxDepth(TreeNode root){
if(root==null){
return 0;
}
int left=maxDepth(root.left);
int right=maxDepth(root.right);
return left>right?left+1:right+1;
}
//判斷二叉樹是不是平衡二叉樹
public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
if(Math.abs(maxDepth(root.left)-maxDepth(root.right))<=1){
return isBalanced(root.left)&&isBalanced(root.right);
}
return false;
}
}
到此這篇關(guān)于Java 數(shù)據(jù)結(jié)構(gòu)進(jìn)階二叉樹題集上的文章就介紹到這了,更多相關(guān)Java 二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了Java獲取此次請求URL以及服務(wù)器根路徑的方法,需要的朋友可以參考下2015-08-08
Java調(diào)用打印機(jī)的2種方式舉例(無驅(qū)/有驅(qū))
我們平時(shí)使用某些軟件或者在超市購物的時(shí)候都會(huì)發(fā)現(xiàn)可以使用打印機(jī)進(jìn)行打印,這篇文章主要給大家介紹了關(guān)于Java調(diào)用打印機(jī)的2種方式,分別是無驅(qū)/有驅(qū)的相關(guān)資料,需要的朋友可以參考下2023-11-11
解決Spring Boot 在localhost域奇怪的404問題(Mac book pro)
這篇文章主要介紹了解決Spring Boot 在localhost域奇怪的404問題(Mac book pro),需要的朋友可以參考下2017-09-09
SpringBoot中實(shí)現(xiàn)定時(shí)任務(wù)的幾種方式
定時(shí)任務(wù)在我們項(xiàng)目開發(fā)中也是很重要的，對于某些場景必須要用定時(shí)任務(wù)?，如定時(shí)發(fā)送郵件啊，定時(shí)統(tǒng)計(jì)數(shù)據(jù)等，這篇文章主要講講項(xiàng)目中實(shí)現(xiàn)定時(shí)任務(wù)的幾種方式,需要的朋友可以參考下2023-05-05
關(guān)于Hadoop中Spark?Streaming的基本概念
這篇文章主要介紹了關(guān)于Hadoop中Spark?Streaming的基本概念,Spark?Streaming是構(gòu)建在Spark上的實(shí)時(shí)計(jì)算框架，它擴(kuò)展了Spark處理大規(guī)模流式數(shù)據(jù)的能力,Spark?Streaming可結(jié)合批處理和交互式查詢,需要的朋友可以參考下2023-07-07
spring學(xué)習(xí)之創(chuàng)建項(xiàng)目 Hello Spring實(shí)例代碼
這篇文章主要介紹了spring學(xué)習(xí)之創(chuàng)建項(xiàng)目 Hello Spring實(shí)例代碼，小編覺得還是挺不錯(cuò)的，具有一定借鑒價(jià)值，需要的朋友可以參考下2018-01-01
springboot2如何禁用自帶tomcat的session功能
這篇文章主要介紹了springboot2如何禁用自帶tomcat的session功能，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-11-11
MyBatis中使用foreach循環(huán)的坑及解決
這篇文章主要介紹了MyBatis中使用foreach循環(huán)的坑及解決方案，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-01-01
下面小編就為大家?guī)砝仙Ｕ凩og4j和Log4j2的區(qū)別(推薦)。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-04-04
什么是注解？用一個(gè)詞就可以描述注解，那就是元數(shù)據(jù)，即一種描述數(shù)據(jù)的數(shù)據(jù)，Java中的注解是如何工作的,需要的朋友可以參考下2015-12-12