Java 數(shù)據(jù)結(jié)構(gòu)進(jìn)階二叉樹(shù)題集上
二叉樹(shù)操作的代碼大多數(shù)使用遞歸來(lái)實(shí)現(xiàn)，代碼會(huì)比較簡(jiǎn)潔，如果使用非遞歸，代碼會(huì)比較的繁榮，而且不易理解。（上）中的題偏向于基礎(chǔ)，后面（下）中的題機(jī)會(huì)比較難。
1、二叉樹(shù)的遍歷
（1）前、中、后序遍歷
這里寫到的遍歷是遞歸遍歷，代碼比較簡(jiǎn)單，后續(xù)會(huì)寫非遞歸的代碼。以前序遍歷為例：
如果根節(jié)點(diǎn)root為空，直接返回，否則，打印根節(jié)點(diǎn)，再分別遞歸root的左子樹(shù)和右子樹(shù)即可。中序遍歷的話，先中序遍歷左子樹(shù)，打印根節(jié)點(diǎn)，再中序遍歷右子樹(shù)即可。
【代碼如下】
//遞歸實(shí)現(xiàn)，比較簡(jiǎ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ì)列來(lái)遍歷鏈表，每次出根節(jié)點(diǎn)，當(dāng)其左右節(jié)點(diǎn)不為空的時(shí)候，入左右節(jié)點(diǎn)。直到隊(duì)列為空，遍歷完成。
如何判斷二叉樹(shù)每層結(jié)點(diǎn)的個(gè)數(shù)？
在對(duì)每層節(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ì)后，我們需要入隊(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、獲取樹(shù)中子結(jié)點(diǎn)的個(gè)數(shù)
通常二叉樹(shù)的問(wèn)題，都會(huì)有兩種思路：遍歷思路和子問(wèn)題思路。
如這道題：
我們可以求出它的左子樹(shù)和右子樹(shù)中子結(jié)點(diǎn)的個(gè)數(shù)，相加即可；或者，定義計(jì)數(shù)器，因?yàn)橐f歸，所以我們需要一個(gè)全局變量（count），遞歸左右子樹(shù)，只要遇到子節(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、獲取二叉樹(shù)的高度
獲取二叉樹(shù)的高度，我們只需要獲取二叉樹(shù)左右子樹(shù)的高度，返回左右子樹(shù)的最大高度加一即可。
【代碼如下】
// 獲取二叉樹(shù)的高度
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、判斷是不是完全二叉樹(shù)
【完全二叉樹(shù)和滿二叉樹(shù)】
- 滿二叉樹(shù): 一棵二叉樹(shù)，如果每層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這棵二叉樹(shù)就是滿二叉樹(shù)。也就是說(shuō)，如果一棵二叉樹(shù)的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是 2^K-1，則它就是滿二叉樹(shù)。
- 完全二叉樹(shù): 完全二叉樹(shù)是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹(shù)是由滿二叉樹(shù)而引出來(lái)的。對(duì)于深度為K的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹(shù)中編號(hào)從0至n-1的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱之為完全二叉樹(shù)。 要注意的是滿二叉樹(shù)是一種特殊的完全二叉樹(shù)。
判斷完全二叉樹(shù)，我們可以借助隊(duì)列來(lái)實(shí)現(xiàn)，在二叉樹(shù)不為空的情況下，對(duì)二叉樹(shù)進(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ì)隊(duì)列中剩下的元素進(jìn)行遍歷，如果全為null，則為完全二叉樹(shù)；如果存在不為null的結(jié)點(diǎn)，則不是完全二叉樹(shù)。
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ì)隊(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è)樹(shù)是否相同
存在以下四種情況：
【代碼如下】
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、另一棵樹(shù)的子樹(shù)
上面已經(jīng)給寫過(guò)判斷兩棵樹(shù)是否相等的題，我們只需要判斷樹(shù)p是否等于樹(shù)q，或者數(shù)p的左子樹(shù)或右子樹(shù)是否等于樹(shù)q。分為以下幾種情況：
【代碼如下】
class Solution {
//判斷兩個(gè)樹(shù)是否相等
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);
}
//判斷子樹(shù)
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、判斷平衡二叉樹(shù)
高度平衡二叉樹(shù)定義為：
一個(gè)二叉樹(shù)每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò) 1 。
首先我們需要寫一個(gè)函數(shù)來(lái)求二叉樹(shù)的高度，只要這個(gè)二叉樹(shù)的左右子樹(shù)高度差不大于1，且左右子樹(shù)都是平衡二叉樹(shù)，則其為平衡二叉樹(shù)。
【代碼如下】
class Solution {
//求二叉樹(shù)的高度
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;
}
//判斷二叉樹(shù)是不是平衡二叉樹(shù)
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)階二叉樹(shù)題集上的文章就介紹到這了,更多相關(guān)Java 二叉樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
SpringMVC中使用@PathVariable綁定路由中的數(shù)組的方法
這篇文章主要介紹了SpringMVC中使用@PathVariable綁定路由中的數(shù)組的方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-07-07
這篇文章主要介紹了java實(shí)現(xiàn)屏蔽詞功能，類似貼吧里面屏蔽各種用戶的發(fā)帖內(nèi)容，感興趣的小伙伴們可以參考一下2015-12-12
在Java編程環(huán)境中,處理zip壓縮文件是一項(xiàng)常見(jiàn)的任務(wù),特別是在數(shù)據(jù)傳輸、備份或者打包應(yīng)用程序時(shí),本文將詳細(xì)講解Java處理壓縮文件的步驟,并有相關(guān)的代碼示例供大家參考,需要的朋友可以參考下2024-10-10
Springboot指定掃描路徑的實(shí)現(xiàn)示例
本文主要介紹了Springboot指定掃描路徑的實(shí)現(xiàn)示例,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2024-05-05
mybatis整合ehcache做三級(jí)緩存的實(shí)現(xiàn)方法
ehcache是一個(gè)快速內(nèi)存緩存框架,java項(xiàng)目里用起來(lái)很方便,下面這篇文章主要給大家介紹了關(guān)于mybatis整合ehcache做三級(jí)緩存的實(shí)現(xiàn)方法,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-06-06
這篇文章主要介紹了怎么用Java來(lái)創(chuàng)建和使用Swing中的幾種常用按鈕，按鈕是我們經(jīng)常要用的工具，但是你有想過(guò)自己怎么去實(shí)現(xiàn)它嗎，感興趣的朋友跟隨文章往下看看吧2022-04-04
MyBatis中高級(jí)多表查詢(ResultMap、association、collection)詳解
文章主要介紹了MyBatis中高級(jí)多表查詢的四種方式：ResultMap、association、collection以及自連接查詢,通過(guò)定義接口的抽象方法、編寫mapper.xml和測(cè)試類,詳細(xì)展示了如何根據(jù)復(fù)雜數(shù)據(jù)結(jié)構(gòu)進(jìn)行數(shù)據(jù)的裝配和查詢,感興趣的朋友一起看看吧2024-11-11
IDEA2023版本創(chuàng)建Spring項(xiàng)目只能勾選17和21卻無(wú)法使用Java8的完美解決方案
想創(chuàng)建一個(gè)springboot的項(xiàng)目，本地安裝的是1.8，但是在使用Spring Initializr創(chuàng)建項(xiàng)目時(shí)，發(fā)現(xiàn)版本只有17和21，這篇文章主要介紹了IDEA2023版本創(chuàng)建Sping項(xiàng)目只能勾選17和21，卻無(wú)法使用Java8的解決方法,需要的朋友可以參考下2023-12-12
SpringBoot集成iTextPDF時(shí),創(chuàng)建PDF文檔涉及Document、PdfPTable和PdfPCell對(duì)象,設(shè)置文檔大小和頁(yè)邊距,使用Paragraph設(shè)置段落樣式,并通過(guò)Table和Cell控制表格樣式和對(duì)齊,還可加入圖片美化文檔,這些步驟對(duì)于生成具有中文內(nèi)容的PDF文件至關(guān)重要2024-09-09
SpringBoot整合SpringSecurity實(shí)現(xiàn)認(rèn)證攔截的教程
我們寫的任何一個(gè)項(xiàng)目，都應(yīng)該有安全防護(hù)，不應(yīng)該讓這個(gè)項(xiàng)目進(jìn)行“裸奔”，否則很容易被別人進(jìn)行攻擊。而在SpringBoot環(huán)境中，其實(shí)可以很容易實(shí)現(xiàn)安全保護(hù)，本文給大家介紹SpringBoot如何整合SpringSecurity實(shí)現(xiàn)認(rèn)證攔截,需要的朋友可以參考下2023-05-05