二叉樹的學習

目錄

樹型結構（了解）

概念

概念（重要）

樹的表示形式（了解）

樹的應用

二叉樹（重點）

概念

兩種特殊的二叉樹

二叉樹的性質

利用性質做題（關鍵）

二叉樹的存儲

二叉樹的基本操作

前置說明

二叉樹的遍歷

二叉樹的基本操作

面試題

樹型結構（了解）

概念

樹是一種非線性的數據結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合。把它叫做樹是因為它看 起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。

它具有以下的特點：

·有一個特殊的結點，稱為根結點，根結點沒有前驅結點

·除根結點外，其余結點被分成M(M > 0)個互不相交的集合T1、T2、......、Tm，其中每一個集合Ti (1<=i<=m)又是一棵與樹類似的子樹。每棵子樹的根結點有且只有一個前驅，可以有0個或多個后繼

·樹是遞歸定義的。

注：

1.子樹是不相交的；

2.除根節點外，每個結點有且僅有一個父節點

3.一顆N個節點的樹有N-1條邊

概念（重要）

結點的度：一個結點含有子樹的個數稱為該結點的度； 如上圖：A的度為6【因為A下面有B,C,D,E,F,G這六個節點，所以A的度為6;】

樹的度：一棵樹中，所有結點度的最大值稱為樹的度； 如上圖：樹的度為6

葉子結點或終端結點：度為0的結點稱為葉結點； 如上圖：B、C、H、I...等節點為葉結點

雙親結點或父結點：若一個結點含有子結點，則這個結點稱為其子結點的父結點； 如上圖：A是B的父結點

孩子結點或子結點：一個結點含有的子樹的根結點稱為該結點的子結點； 如上圖：B是A的孩子結點

根結點：一棵樹中，沒有雙親結點的結點；如上圖：A

結點的層次：從根開始定義起，根為第1層，根的子結點為第2層，以此類推

樹的高度或深度：樹中結點的最大層次； 如上圖：樹的高度為4

樹的以下概念只需了解，在看書時只要知道是什么意思即可：

非終端結點或分支結點：度不為0的結點； 如上圖：D、E、F、G...等節點為分支結點

兄弟結點：具有相同父結點的結點互稱為兄弟結點； 如上圖：B、C是兄弟結點

堂兄弟結點：雙親在同一層的結點互為堂兄弟；如上圖：H、I互為兄弟結點

結點的祖先：從根到該結點所經分支上的所有結點；如上圖：A是所有結點的祖先

子孫：以某結點為根的子樹中任一結點都稱為該結點的子孫。如上圖：所有結點都是A的子孫

森林：由m（m>=0）棵互不相交的樹組成的集合稱為森林

樹的表示形式（了解）

樹結構相對線性表就比較復雜了，要存儲表示起來就比較麻煩了，實際中樹有很多種表示方式，如：雙親表示法， 孩子表示法、孩子雙親表示法、孩子兄弟表示法等等。我們這里就簡單的了解其中最常用的孩子兄弟表示法。

class Node {int value; // 樹中存儲的數據Node ?rstChild; // 第一個孩子引用Node nextBrother; // 下一個兄弟引用
}

其表示方法如下圖所示

樹的應用

文件系統管理（目錄和文件）

二叉樹（重點）

概念

一棵二叉樹是結點的一個有限集合，該集合：

1. 或者為空

2. 或者是由一個根節點加上兩棵別稱為左子樹和右子樹的二叉樹組成。

從上圖可以看出：

1. 二叉樹不存在度大于2的結點【重要】

2. 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹 注意：對于任意的二叉樹都是由以下幾種情況復合而成的：

兩種特殊的二叉樹

1. 滿二叉樹: 一棵二叉樹，如果每層的結點數都達到最大值，則這棵二叉樹就是滿二叉樹。也就是說，如果一棵 二叉樹的層數為K，且結點總數是2^k-1，則它就是滿二叉樹。

2. 完全二叉樹: 完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n 個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從0至n-1的結點一一對應時稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。【從上到下，從左到右依次存放】

二叉樹的性質

1. 若規定根結點的層數為1，則一棵非空二叉樹的第i層上最多有 2^(i-1)(i>0)個結點

2. 若規定只有根結點的二叉樹的深度為1，則深度為K的二叉樹的最大結點數是2^k-1 (k>=0)

3. 對任何一棵二叉樹, 如果其葉結點個數為 n0, 度為2的非葉結點個數為 n2,則有n0＝n2＋1【對于任何一顆二叉樹，葉子節點的個數永遠比度為2的節點個數多1】

推導：一顆N個節點的樹有N-1條邊

在任意一顆二叉樹中，葉子節點的個數為n0，度為1的結點個數為n1，度為2的節點個數為n2，則會產生總的結點個數:N = n0+n1+n2;且度為0的節點向下不會產生邊，度為1的節點向下會產生n1條邊，度為2的節點向下會產生2*n2條邊，總共產生的邊數：N-1=n1+2*n2; 將兩個式子聯立即可得出答案。

4. 具有n個結點的完全二叉樹的深度k為 log2(n+1)上取整

5. 對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的順序對所有節點從0開始編號，則對于序號為i 的結點有：

·若i>0，雙親序號：(i-1)/2；i=0，i為根結點編號，無雙親結點

·若2i+1<n，左孩子序號：2i+1，否則無左孩子

·若2i+2<n，右孩子序號：2i+2，否則無右孩子

利用性質做題（關鍵）

以下是小編寫的一個題解：

二叉樹的存儲

二叉樹的存儲結構分為：順序存儲和類似于鏈表的鏈式存儲。

二叉樹的鏈式存儲是通過一個一個的節點引用起來的，常見的表示方式有二叉和三叉表示方式，具體如下：主要以孩子表示法為主

// 孩子表示法
class Node {int val; // 數據域Node left; // 左孩子的引用，常常代表左孩子為根的整棵左子樹Node right; // 右孩子的引用，常常代表右孩子為根的整棵右子樹
}// 孩子雙親表示法
class Node {int val; // 數據域Node left; // 左孩子的引用，常常代表左孩子為根的整棵左子樹Node right; // 右孩子的引用，常常代表右孩子為根的整棵右子樹Node parent; ? ?// 當前節點的根節點
}

二叉樹的基本操作

前置說明

在學習二叉樹的基本操作前，需先要創建一棵二叉樹，然后才能學習其相關的基本操作。由于現在大家對二叉樹結 構掌握還不夠深入，為了降低大家學習成本，此處手動快速創建一棵簡單的二叉樹，快速進入二叉樹操作學習，等 二叉樹結構了解的差不多時，我們反過頭再來研究二叉樹真正的創建方式。

以上述這個二叉樹為例子，即創建像上面這個二叉樹；

package BinaryTree;/*** 這里手動創建一個二叉樹*/
public class BinaryTree1 {// 樹是由一個個節點構成的，所有得先把這個節點給構造出來static class TreeNode{private char val;  // 值private TreeNode left;  // 左孩子private TreeNode right; // 右孩子/*再來一個構造方法*/public TreeNode(char val) {this.val = val;}}/*** 還是像剛剛學習鏈表一樣，我們用最淳樸得方法來創建一個二叉樹*/public TreeNode createTree(){TreeNode node1 = new TreeNode('A');TreeNode node2 = new TreeNode('B');TreeNode node3 = new TreeNode('C');TreeNode node4 = new TreeNode('D');TreeNode node5 = new TreeNode('E');TreeNode node6 = new TreeNode('F');TreeNode node7 = new TreeNode('G');TreeNode node8 = new TreeNode('H');node1.left = node2;node1.right = node3;node2.left = node4;node2.right = node5;node5.right = node8;node3.left = node6;node3.right = node7;return node1;  // 返回根節點}}

二叉樹的遍歷

約定的遍歷方式：

前序遍歷(先序遍歷)——訪問根結點--->根的左子樹--->根的右子樹。【根、左、右】

中序遍歷——根的左子樹--->根節點--->根的右子樹。【左、根、右】

后序遍歷——根的左子樹--->根的右子樹--->根節點。【左、右、根】

層序遍歷:除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進行層序遍歷。設二叉樹的根節點所在 層數為1，層序遍歷就是從所在二叉樹的根節點出發，首先訪問第一層的樹根節點，然后從左到右訪問第2層 上的節點，接著是第三層的節點，以此類推，自上而下，自左至右逐層訪問樹的結點的過程就是層序遍歷。

前序遍歷代碼展示：

public  void preOrder(TreeNode root){// root節點一直再變化// 當root節點為空，說明已經打印完了if (root == null){return;}System.out.print(root.val+" ");preOrder(root.left);  // 走完根就先走左邊preOrder(root.right); //走完左邊就走右邊}

中序遍歷代碼展示：

/*** 中序遍歷* @param root*/public void inOrder(TreeNode root){if (root == null){return;}inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}

后序遍歷代碼展示：

/*** 后序遍歷* @param root*/void postOrder(TreeNode root){if (root == null){return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val + " ");}

【練習】請同學們根據以上二叉樹的三種遍歷方式，給出以下二叉樹的：

答案：

前：ABDEHCFG

中：DBEHAFCG

后：DHEBFGCA

選擇題：

解析：

二叉樹的基本操作

代碼展示：

package BinaryTree;import java.util.ArrayList;
import java.util.List;import static java.lang.Math.max;/*** 這里手動創建一個二叉樹*/
public class BinaryTree1 {// 樹是由一個個節點構成的，所有得先把這個節點給構造出來static class TreeNode{private char val;  // 值private TreeNode left;  // 左孩子private TreeNode right; // 右孩子/*再來一個構造方法*/public TreeNode(char val) {this.val = val;}}/*** 還是像剛剛學習鏈表一樣，我們用最淳樸得方法來創建一個二叉樹*/public TreeNode createTree(){TreeNode node1 = new TreeNode('A');TreeNode node2 = new TreeNode('B');TreeNode node3 = new TreeNode('C');TreeNode node4 = new TreeNode('D');TreeNode node5 = new TreeNode('E');TreeNode node6 = new TreeNode('F');TreeNode node7 = new TreeNode('G');TreeNode node8 = new TreeNode('H');node1.left = node2;node1.right = node3;node2.left = node4;node2.right = node5;node5.right = node8;node3.left = node6;node3.right = node7;return node1;  // 返回根節點}/*** 前序遍歷* @param root*/public  void preOrder(TreeNode root){// root節點一直再變化// 當root節點為空，說明已經打印完了if (root == null){return;}System.out.print(root.val+" ");preOrder(root.left);  // 走完根就先走左邊preOrder(root.right); //走完左邊就走右邊}/*** 前序遍歷得升級：將前序遍歷的結果存儲到list當中*/public List<TreeNode> preOrder2(TreeNode root){List<TreeNode> list = new ArrayList<>();if (root == null){return list;}list.add(root);List<TreeNode> leftTree = preOrder2(root.left);list.addAll(leftTree);List<TreeNode> rightTree = preOrder2(root.left);list.addAll(rightTree);return list;}/*** 中序遍歷* @param root*/public void inOrder(TreeNode root){if (root == null){return;}inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}/*** 后序遍歷* @param root*/void postOrder(TreeNode root){if (root == null){return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val + " ");}public int size = 0;/*** 獲取樹中節點的個數** 思路1：* 以前序遍歷/中序遍歷/后序遍歷 遍歷這棵樹的時候，* 每個節點都會遍歷到，遍歷一次節點我們就計數一次** 思路2：子問題思路* 要算當前root總共有多少個節點，其實就等于=左數的節點的個數+右樹的節點的個數+1** @param root* @return*/public int size(TreeNode root){if (root == null){return 0;  // 如果樹為空【即為0個節點】}size++;size(root.left);size(root.right);return size;}public int size1(TreeNode root){if (root == null){return 0;  // 如果樹為空【即為0個節點】}return size1(root.left)+size1(root.right)+1;}public int leafSize = 0;/*** 獲取葉子節點的個數* 思路1：* 先遍歷【前序/中序/后序都行】* 如果root左右都為空，說明他就是一個葉子** 思路2：子問題的思路* 要求當前root有多少個節點，其實就相當于求root左樹的葉子+root右樹的葉子=整一棵樹的葉子* @param root* @return*/public void getLeafNodeCount(TreeNode root){// 如果它是一棵空樹，就什么都不做if (root == null){return;}// 如果他不為空就要判斷根節點左右是不是都為空，都為空則加1if (root.left == null && root.right == null){leafSize++;}getLeafNodeCount(root.left);getLeafNodeCount(root.right);}public int getLeafNodeCount2(TreeNode root){// 如果它是一棵空樹，就什么都不做if (root == null){return 0;}if (root.left == null && root.right == null){return 1;}return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);}/*** 獲取第K層節點的個數* @param root* @param k* @return* 思路1：遍歷* 思路2：子問題* root這棵樹的第K層 = root.left的K-1層 + root.right的K-1層***/public int getKLevelNodeCount(TreeNode root,int k){if (root == null){return 0;}if (k==1){//到達第K層return 1;}return getKLevelNodeCount(root.left, k-1)+getKLevelNodeCount(root.right,k-1);}/*** 獲取二叉樹的高度* @param root* @return* 思路：子問題思路* root這棵樹的高度就是 root左樹這棵樹和root右樹這棵樹的最大值*/public int getHeight(TreeNode root){// 如果這棵樹是一顆空樹,自然就沒有深度了if (root == null){return 0;}return max(getHeight(root.left),getHeight(root.right))+1;}/*** 檢測值為value的元素是否存在* @param root* @param val* @return* 思路1：以前序遍歷的方式進行遍歷*/public boolean find(TreeNode root, char val){if (root == null){return false;}if (root.val == val){return true;}boolean leftVal = find(root.left,val);  // 先去我的左樹找if (leftVal == true){return true;}//  如果我的左樹找不到再去我的右樹找boolean rightVal = find(root.right,val);  // 先去我的右樹找if (rightVal == true){return true;}return false;}/***  層序遍歷*/public void levelOrder(TreeNode root){}/*** 判斷一棵樹是不是完全二叉樹* @param root* @return*/public boolean isCompleteTree(TreeNode root){return false;}}

測試代碼：

package BinaryTree;
/*** 這個代碼下主要是二叉樹的一個方法的測試*/
public class Test {public static void main(String[] args) {BinaryTree1 binaryTree1 = new BinaryTree1();   // 實例化一個二叉樹對象BinaryTree1.TreeNode root = binaryTree1.createTree();   // 創建一個二叉樹對象,返回根節點System.out.println("=============");binaryTree1.preOrder(root);System.out.println();  // 來一個回車binaryTree1.inOrder(root);System.out.println();binaryTree1.postOrder(root);System.out.println();System.out.println("=============");/*** 下面是一些二叉樹的一些常規操作的代碼*/// 1.測試節點個數int size = binaryTree1.size(root);System.out.println("該二叉樹的節點樹為："+size);int size1 = binaryTree1.size1(root);System.out.println("該二叉樹的節點樹為："+size1);System.out.println("=============");// 2.測試葉子節點個數binaryTree1.getLeafNodeCount(root);System.out.println("該二叉樹葉子節點的個數："+binaryTree1.leafSize);System.out.println("該二叉樹葉子節點的個數："+binaryTree1.getLeafNodeCount2(root));System.out.println("=============");// 3.測試第K層有多少個節點int count = binaryTree1.getKLevelNodeCount(root, 2);System.out.println("該二叉樹第2層的節點個數："+count);System.out.println("=============");// 4.測試一下這棵樹的高度int hight = binaryTree1.getHeight(root);System.out.println("該二叉樹的高度為："+hight);System.out.println("=============");// 5.檢測值為value的元素是否存在boolean result1 = binaryTree1.find(root,'E');if (result1 == true){System.out.println("在該二叉樹中找到了這個節點");}else {System.out.println("該二叉樹中沒有這個節點");}boolean result2 = binaryTree1.find(root,'Z');if (result2 == true){System.out.println("在該二叉樹中找到了這個節點");}else {System.out.println("該二叉樹中沒有這個節點");}}}

面試題

1. 檢查兩顆樹是否相同?100. 相同的樹 - 力扣（LeetCode）

何為相同：如果兩棵樹在結構上是相同的，而且節點上的值也是相同的

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {// 如果一個為空，另外一個不為空，則這兩顆樹一定是不相等的if(q != null && p == null || q == null && p != null){return false;}// 兩個都為空if(q == null && p == null){return true;}// 如果兩個都不為空呢if(p.val != q.val){return false;}return isSameTree(q.left,p.left) && isSameTree(p.right,q.right);}
}

2. 另一顆樹的子樹

572. 另一棵樹的子樹 - 力扣（LeetCode）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {/**這個代碼是判斷兩棵樹是不是一個相同的樹*/public boolean isSameTree(TreeNode p, TreeNode q) {// 如果一個為空，另外一個不為空，則這兩顆樹一定是不相等的if(q != null && p == null || q == null && p != null){return false;}// 兩個都為空if(q == null && p == null){return true;}// 如果兩個都不為空呢if(p.val != q.val){return false;}return isSameTree(q.left,p.left) && isSameTree(p.right,q.right);}public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root == null){return false;}// 如果只有一個節點if(isSameTree(root,subRoot)){return true;}if(isSubtree(root.left,subRoot)){return true;}if(isSubtree(root.right,subRoot)){return true;}return false;}
}

注：寫這種遍歷題的時候，需要注意“空指針異常”

3. 翻轉二叉樹

226. 翻轉二叉樹 - 力扣（LeetCode）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode invertTree(TreeNode root) {// 如果該樹為空if (root == null) {return null;}// 交換左右子樹TreeNode temp = root.left;root.left = root.right;root.right = temp;// 遞歸反轉左右子樹invertTree(root.left);invertTree(root.right);return root;}
}

4. 判斷一顆二叉樹是否是平衡二叉樹

110. 平衡二叉樹 - 力扣（LeetCode）

核心思路：只有每一顆子樹都是高度平衡的，才能說這棵樹是高度平衡的

代碼示例1：效率較低

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int getHeight(TreeNode root){// 如果這棵樹是一顆空樹,自然就沒有深度了if (root == null){return 0;}return Math.max(getHeight(root.left), getHeight(root.right)) + 1;}public boolean isBalanced(TreeNode root) {// 如果是空樹，就一定是一顆平衡樹if(root == null){return true;}if(getHeight(root.left)-getHeight(root.right)>1 || getHeight(root.right)-getHeight(root.left)>1){return false;}return isBalanced(root.left) && isBalanced(root.right);}
}

代碼示例2：減少重復計算

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int getHeight(TreeNode root){// 如果這棵樹是一顆空樹,自然就沒有深度了if (root == null){return 0;}int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);if(Math.abs(leftHeight-rightHeight)<=1 && leftHeight>=0 && rightHeight>=0){return Math.max(leftHeight,rightHeight)+1;}else{return -1;   // 當返回的是一個復數的時候，一定是不平衡}}public boolean isBalanced(TreeNode root) {// 如果是空樹，就一定是一顆平衡樹if(root == null){return true;}return getHeight(root) >= 0;}
}

5. 對稱二叉樹

101. 對稱二叉樹 - 力扣（LeetCode）

代碼示例1：內存損耗比較多

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isMirror(TreeNode p, TreeNode q) {// 如果一個為空，另一個不為空，則不對稱if (p == null && q == null) {return true;}if (p == null || q == null) {return false;}// 遞歸判斷對稱性：左子樹的左子樹 vs 右子樹的右子樹，左子樹的右子樹 vs 右子樹的左子樹return (p.val == q.val) && isMirror(p.left, q.right) && isMirror(p.right, q.left);
}public boolean isSymmetric(TreeNode root) {if (root == null) {return true;}return isMirror(root.left, root.right);
}}

6. 二叉樹的構建及遍歷

二叉樹遍歷_牛客題霸_牛客網

編一個程序，讀入用戶輸入的一串先序遍歷字符串，根據此字符串建立一個二叉樹（以指針方式存儲）。 例如如下的先序遍歷字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空樹。建立起此二叉樹以后，再對二叉樹進行中序遍歷，輸出遍歷結果。

import java.util.Scanner;// 定義一個節點
class TreeNode{char key;  // 因為是字符串類型的TreeNode left;TreeNode right;// 給一個不帶參數的構造方法public TreeNode(){}// 給一個帶參數的構造方法public TreeNode(char key){this.key = key;}
}// 注意類名必須為 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的區別while (in.hasNextLine()) { // 注意 while 處理多個 caseString str = in.nextLine();TreeNode root = createTree(str);inorder(root);}}public static int i = 0;// 來一個創建二叉樹的方法public static TreeNode createTree(String str){TreeNode root = null;if(str.charAt(i) != '#'){root = new TreeNode(str.charAt(i));i++;root.left = createTree(str);root.right = createTree(str);}else{i++;}return root;}// 中序遍歷public static void inorder(TreeNode root){if(root == null){return;}inorder(root.left);System.out.print(root.key+" ");inorder(root.right);}}

7. 二叉樹的分層遍歷

102. 二叉樹的層序遍歷 - 力扣（LeetCode）

思路一：采用隊列

思路如上圖所示，我們是利用以一個隊列來存儲我們的中間數據

public void levelOrder(TreeNode root){// 如果根節點為空，則直接返回，什么都不輸出if (root == null){return;}Queue<TreeNode> queue = new LinkedList<>();  // 創建一個隊列來放元素的queue.offer(root);while (!queue.isEmpty()) {  // 只要隊列不為空，就繼續遍歷TreeNode cur = queue.poll();  // 取出隊首元素System.out.print(cur.val + " ");  // 訪問該節點// 將左子節點加入隊列if (cur.left != null) {queue.offer(cur.left);}// 將右子節點加入隊列if (cur.right != null) {queue.offer(cur.right);}}}

思路2：使用順序表

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {// 如果根節點為空，則直接返回，什么都不輸出List<List<Integer>> list = new ArrayList<>();if (root == null){return list;}Queue<TreeNode> queue = new LinkedList<>();  // 創建一個隊列來放元素的queue.offer(root);while (!queue.isEmpty()){// 求一下當前隊列的大小int size = queue.size();List<Integer> tmp = new ArrayList<>();while (size!=0){TreeNode cur = queue.poll();tmp.add(cur.val);size--;if (cur.left != null){queue.offer(cur.left);}if (cur.right != null){queue.offer(cur.right);}}list.add(tmp);}return list;}
}

8. 給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先

236. 二叉樹的最近公共祖先 - 力扣（LeetCode）

三種情況：

代碼展示1：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {/**先判斷幾種特殊情況*/if(root == null){return null;}if(p == root || q == root){return root;}/**如果上述幾種情況都不滿足的話*/TreeNode leftroot = lowestCommonAncestor(root.left,p,q);TreeNode rightroot = lowestCommonAncestor(root.right,p,q);if(leftroot!=null && rightroot!=null){// 說明分別在root左右兩邊找到了p,qreturn root;}else if(rightroot == null){// 說明在左邊return leftroot;}else{return rightroot;}}
}

代碼展示2：更簡便【鏈表的相交節點】

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {Stack<TreeNode> stackP = new Stack<>();Stack<TreeNode> stackQ = new Stack<>();public boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack){if(root == null || node == null){return false;}stack.push(root);if(root == node){return true;}boolean flg1 = getPath(root.left,node,stack);if(flg1){return true;}boolean flg2 = getPath(root.right,node,stack);if(flg2){return true;}stack.pop();return false;}public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null){return null;}getPath(root,p,stackP);getPath(root,q,stackQ);int sizeP = stackP.size();int sizeQ = stackQ.size();if(sizeP > sizeQ){for(int i = 0;i<sizeP-sizeQ;i++){stackP.pop();}}if(sizeQ > sizeP){for(int i = 0;i<sizeQ-sizeP;i++){stackQ.pop();}}while(stackP!=null && stackQ!=null){TreeNode nodeP = stackP.pop();TreeNode nodeQ = stackQ.pop();if(nodeP == nodeQ){return nodeP;}}return null;}
}

9. 根據一棵樹的前序遍歷與中序遍歷構造二叉樹。

105. 從前序與中序遍歷序列構造二叉樹 - 力扣（LeetCode）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {return helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);}private TreeNode helper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {if (preStart > preEnd || inStart > inEnd) return null;int rootVal = preorder[preStart]; // 先序遍歷的第一個值是根節點TreeNode root = new TreeNode(rootVal);// 在 inorder 里找到 rootVal 的索引int rootIndex = inStart;while (rootIndex <= inEnd && inorder[rootIndex] != rootVal) {rootIndex++;}int leftSize = rootIndex - inStart; // 左子樹大小// 遞歸構造左子樹root.left = helper(preorder, preStart + 1, preStart + leftSize, inorder, inStart, rootIndex - 1);// 遞歸構造右子樹root.right = helper(preorder, preStart + leftSize + 1, preEnd, inorder, rootIndex + 1, inEnd);return root;}}

10. 根據一棵樹的中序遍歷與后序遍歷構造二叉樹

106. 從中序與后序遍歷序列構造二叉樹 - 力扣（LeetCode）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {return helper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);}private TreeNode helper(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {if (inStart > inEnd || postStart > postEnd) return null;int rootVal = postorder[postEnd]; // 后序遍歷的最后一個值是根節點TreeNode root = new TreeNode(rootVal);// 在 inorder 里找到 rootVal 的索引int rootIndex = inStart;while (rootIndex <= inEnd && inorder[rootIndex] != rootVal) {rootIndex++;}int leftSize = rootIndex - inStart; // 左子樹大小// 遞歸構造左子樹root.left = helper(inorder, inStart, rootIndex - 1, postorder, postStart, postStart + leftSize - 1);// 遞歸構造右子樹root.right = helper(inorder, rootIndex + 1, inEnd, postorder, postStart + leftSize, postEnd - 1);return root;}
}

11. 二叉樹創建字符串

606. 根據二叉樹創建字符串 - 力扣（LeetCode）

自己去AI，因為比較難；

12. 二叉樹前序非遞歸遍歷實現?

144. 二叉樹的前序遍歷 - 力扣（LeetCode）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if(root == null){return list;  //直接返回，有可能list也是一個空的}list.add(root.val);List<Integer> LeftTree = preorderTraversal(root.left);  // 處理左子樹list.addAll(LeftTree);List<Integer> RightTree = preorderTraversal(root.right);  // 處理左子樹list.addAll(RightTree);return list;}
}

13. 二叉樹中序非遞歸遍歷實現

94. 二叉樹的中序遍歷 - 力扣（LeetCode）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if(root == null){return list;  //直接返回，有可能list也是一個空的}List<Integer> LeftTree = inorderTraversal(root.left);  // 處理左子樹list.addAll(LeftTree);list.add(root.val);List<Integer> RightTree = inorderTraversal(root.right);  // 處理左子樹list.addAll(RightTree);return list;}
}

14. 二叉樹后序非遞歸遍歷實現

145. 二叉樹的后序遍歷 - 力扣（LeetCode）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if(root == null){return list;  //直接返回，有可能list也是一個空的}List<Integer> LeftTree = postorderTraversal(root.left);  // 處理左子樹list.addAll(LeftTree);List<Integer> RightTree = postorderTraversal(root.right);  // 處理左子樹list.addAll(RightTree);list.add(root.val);return list;}
}

15.怎么判斷一棵樹是不是完全二叉樹

如上圖所示，當第一個null后面不全是null，說明這不是一個完全二叉樹。如果第一個空后面全是空，則為一個完全二叉樹。

/*** 判斷一棵樹是不是完全二叉樹* @param root* @return*/public boolean isCompleteTree(TreeNode root){// 如果根節點為空，則直接返回，什么都不輸出if (root == null){return true;}Queue<TreeNode> queue = new LinkedList<>();  // 創建一個隊列來放元素的queue.offer(root);while (!queue.isEmpty()) {  // 只要隊列不為空，就繼續遍歷TreeNode cur = queue.poll();  // 取出隊首元素if (cur != null){queue.offer(cur.left);queue.offer(cur.right);}else {break;  // 退出該循環【也是說明碰到了一個null】}}while (!queue.isEmpty()){if (queue.poll() != null){return false;}}return true;}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/pingmian/73205.shtml
繁體地址，請注明出處：http://hk.pswp.cn/pingmian/73205.shtml
英文地址，請注明出處：http://en.pswp.cn/pingmian/73205.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

AbMole新生大鼠腦類器官培養Protocol

AbMole新生大鼠腦類器官培養Protocol

近日&#xff0c;希臘亞里士多德大學塞薩洛尼基分校的研究團隊在《神經科學方法》&#xff08;Journal of Neuroscience Methods&#xff09;期刊上發表了一項引人注目的研究&#xff0c;他們開發了一種基于新生大鼠腦組織的新型類器官培養協議&#xff0c;并展望其在阿爾茨海默…
閱讀更多...
物理環境與安全

物理環境與安全

物理安全的重要性 信息系統安全戰略的一個重要組成部分物理安全面臨問題 環境風險不確定性人類活動的不可預知性 典型的物理安全問題 自然災害環境因素設備安全、介質安全、傳輸安全 場地選擇 區域&#xff1a;避開自然災害高發區環境&#xff1a;原理可能的危險因素抗震&…
閱讀更多...
手動離線安裝NextCloud插件

手動離線安裝NextCloud插件

1、下載離線插件安裝包 進入NextCloud官方插件商城&#xff1a;https://apps.nextcloud.com/ 選擇自己需要的插件軟件 選擇NextCloud對應版本的插件安裝包 2、解壓安裝 進入的到NextCloud安裝目錄的apps目錄 cd /var/www/html/apps 將下載的xxx.tar.gz復制到apps目錄中解…
閱讀更多...
算力100問?第93問：算力資源為何更分散了？

算力100問?第93問：算力資源為何更分散了？

目錄 1、政策驅動與地方投資的盲目性 2、美國芯片斷供與國產替代的陣痛 3、政企市場對私有云的偏好 4、技術標準與供需結構的失衡 5、產業生態與市場機制的滯后 6、破局路徑與未來展望 在大模型和人工智能技術快速發展的背景下，算力資源已成為數字經濟時代的核心基礎設施…
閱讀更多...
基于HTML的郵件發送狀態查詢界面設計示例

基于HTML的郵件發送狀態查詢界面設計示例

以下是一個基于HTML的郵件發送狀態查詢界面設計示例&#xff0c;結合篩選功能、狀態展示和重新發送操作&#xff0c;采用Bootstrap框架實現響應式布局&#xff1a; <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"&…
閱讀更多...
分治-快速排序系列一＞快速排序

分治-快速排序系列一＞快速排序

目錄 題目方法&#xff1a;優化方法&#xff1a;代碼&#xff1a; 題目方法&#xff1a; 忘記快速排序看這里&#xff1a;鏈接: link 優化方法&#xff1a; 代碼&#xff1a; public int[] sortArray(int[] nums) {qsort(nums,0,nums.length-1);return nums;}private void qso…
閱讀更多...
《AI大模型趣味實戰 》第7集：多端適配 個人新聞頭條 基于大模型和RSS聚合打造個人新聞電臺(Flask WEB版) 1

《AI大模型趣味實戰 》第7集：多端適配 個人新聞頭條 基于大模型和RSS聚合打造個人新聞電臺(Flask WEB版) 1

AI大模型趣味實戰 第7集&#xff1a;多端適配 個人新聞頭條 基于大模型和RSS聚合打造個人新聞電臺(Flask WEB版) 1 摘要 在信息爆炸的時代&#xff0c;如何高效獲取和篩選感興趣的新聞內容成為一個現實問題。本文將帶領讀者通過Python和Flask框架&#xff0c;結合大模型的強大…
閱讀更多...
微服務 - 中級篇

微服務 - 中級篇

微服務 - 中級篇 一、微服務架構深化&#xff08;一&#xff09;服務拆分原則&#xff08;二&#xff09;服務通信方式 二、微服務技術選型&#xff08;一&#xff09;開發框架&#xff08;二&#xff09;容器技術 三、微服務實踐與優化&#xff08;后續會詳細分析&#xff09;…
閱讀更多...
STM32__紅外避障模塊的使用

STM32__紅外避障模塊的使用

目錄 一、紅外避障模塊 概述 二、直接讀取OUT引腳電平 三、使用中斷方式觸發 一、紅外避障模塊 概述 引腳解釋&#xff1a; VCC接3.3V 或 5.0VGND接開發板的GNDOUT數字量輸出(0或1&#xff09;; 低電平時表示前方有障礙 ; 通過可調電阻調整檢測距離 產品特點&#xff1a; …
閱讀更多...
【AI大模型】DeepSeek + 通義萬相高效制作AI視頻實戰詳解

【AI大模型】DeepSeek + 通義萬相高效制作AI視頻實戰詳解

目錄 一、前言 二、AI視頻概述 2.1 什么是AI視頻 2.2 AI視頻核心特點 2.3 AI視頻應用場景 三、通義萬相介紹 3.1 通義萬相概述 3.1.1 什么是通義萬相 3.2 通義萬相核心特點 3.3 通義萬相技術特點 3.4 通義萬相應用場景 四、DeepSeek 通義萬相制作AI視頻流程 4.1 D…
閱讀更多...
帆軟第二題 - 多源報表

帆軟第二題 - 多源報表

第二題&#xff0c;多源報表 實現功能&#xff1a; 多源報表&#xff1a;供應商與所在地區來源于表PRODUCER 明細來源于表PRODUCT 分組報表&#xff1a;按組顯示數據&#xff0c;每個供應商對應其產品明細 按組分頁&#xff1a;每個供應商一頁 表頭重復&#xff1a; 數據…
閱讀更多...
SVN忽略不必提交的文件夾和文件方法

SVN忽略不必提交的文件夾和文件方法

最近有小伙伴在問&#xff1a;SVN在提交時如何忽略不必提交的文件夾和文件&#xff0c;如node_modules&#xff0c;.git&#xff0c;.idea等&#xff1f; 操作其實很簡單&#xff0c;下面直接上圖&#xff1a; 第一步&#xff1a; 第二步&#xff1a; 最后一步&#xff1a; 第…
閱讀更多...
Uthana，AI 3D角色動畫生成平臺

Uthana，AI 3D角色動畫生成平臺

Uthana是什么 Uthana 是專注于3D角色動畫生成的AI平臺。平臺基于簡單的文字描述、參考視頻或動作庫搜索&#xff0c;快速為用戶生成逼真的動畫&#xff0c;支持適配任何骨骼結構的模型。Uthana 提供風格遷移、API集成和定制模型訓練等功能&#xff0c;滿足不同用戶需求。平臺提…
閱讀更多...
六十天前端強化訓練之第二十九天之深入解析：從零構建企業級Vue項目的完整指南

六十天前端強化訓練之第二十九天之深入解析：從零構建企業級Vue項目的完整指南

歡迎來到編程星辰海的博客講解 看完可以給一個免費的三連嗎&#xff0c;謝謝大佬&#xff01; 目錄 一、Vite核心原理與開發優勢 二、項目創建深度解析 三、配置體系深度剖析 四、企業級項目架構設計 五、性能優化實戰 六、開發提效技巧 七、質量保障體系 八、擴展閱讀…
閱讀更多...
Ceph集群2025（Squid版）導出高可用NFS集群(上集)

Ceph集群2025（Squid版）導出高可用NFS集群(上集)

#創建一個CephFS 文件系統 ceph fs volume create cephfs02#創建子卷 ceph fs subvolumegroup create cephfs02 myfsg2#查看子卷 ceph fs subvolumegroup ls cephfs02[{"name": "myfsg2"} ]創建 NFS Ganesha 集群 #例子 $ ceph nfs cluster create <c…
閱讀更多...
第2.3節 Android生成全量和增量報告

第2.3節 Android生成全量和增量報告

覆蓋率報告&#xff08;Coverage Report&#xff09;是一種軟件測試工具生成的報告&#xff0c;用于評估測試用例對代碼的覆蓋程度。它通過統計代碼中哪些部分已經被測試用例執行過&#xff0c;哪些部分還沒有被執行&#xff0c;來衡量測試的充分性。覆蓋率報告通常包括以下幾種…
閱讀更多...
奇跡科技：藍牙網關賦能少兒籃球教育的創新融合案例研究

奇跡科技：藍牙網關賦能少兒籃球教育的創新融合案例研究

一、引言 本文研究了福建奇跡運動體育科技有限公司&#xff08;簡稱‘奇跡科技’&#xff09;如何利用其創新產品體系和桂花網藍牙網關M1500&#xff0c;與少兒籃球教育實現深度融合。重點分析其在提升教學效果、保障訓練安全、優化個性化教學等方面的實踐與成效&#xff0c;為…
閱讀更多...
高考志愿填報管理系統基于Spring Boot SSM

高考志愿填報管理系統基于Spring Boot SSM

目錄 摘要 ?一、系統需求分析?&#xff1a; 1.1用戶主體分析 1.2 功能需求分析 1.3、非功能需求分析 二、?技術實現?&#xff1a; ?三、結論?&#xff1a; 摘要 該系統主要實現了&#xff1a;學生信息管理、院校信息查詢、專業信息展示、志愿填報模擬、智能推薦管…
閱讀更多...
網絡HTTPS協議

網絡HTTPS協議

Https HTTPS&#xff08;Hypertext Transfer Protocol Secure&#xff09;是 HTTP 協議的加密版本&#xff0c;它使用 SSL/TLS 協議來加密客戶端和服務器之間的通信。具體來說&#xff1a; ? 加密通信&#xff1a;在用戶請求訪問一個 HTTPS 網站時&#xff0c;客戶端&#x…
閱讀更多...
LintCode第1712題 - 和相同的二元子數組

LintCode第1712題 - 和相同的二元子數組

描述 在由若干 0 和 1 組成的數組 A 中&#xff0c;有多少個和為 S 的非空子數組 樣例 1: 輸入&#xff1a;A [1,0,1,0,1], S 2 輸出&#xff1a;4 解釋&#xff1a; 如下面黑體所示&#xff0c;有 4 個滿足題目要求的子數組&#xff1a; [1,0,1] [1,0,1] [1,0,1,0] [0,1,…
閱讀更多...
最新文章

Copyright @ 2022~2023