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