目錄
一、樹
1、初識樹
2、樹的一些概念
3、樹的表示形式
二、二叉樹
1、初識二叉樹
2、兩種特殊的二叉樹
3、二叉樹的性質(zhì)?
4、二叉樹的遍歷
5、實現(xiàn)一棵二叉樹?
6、二叉樹題目（沒代碼的后面會給補上）
一、樹
1、初識樹
（1）根節(jié)點沒有前驅(qū)。
（2）子樹的根節(jié)點只有一個前驅(qū)，可以有0個或多個后繼。
（3）每個子樹都是不相交的，子樹之間不能有交集。
（4）N個結(jié)點有N-1條邊
2、樹的一些概念
1、結(jié)點的度：這個結(jié)點有幾個子樹，度就為幾
2、樹的度：所有結(jié)點度的最大值就是樹的度
3、根結(jié)點：沒有前驅(qū)的結(jié)點
4、葉子結(jié)點或終端結(jié)點：沒有后繼的結(jié)點（沒有子樹），即度為0的結(jié)點
5、分支結(jié)點或非終端結(jié)點：有后繼的結(jié)點（有子樹），即度不為0的結(jié)點
6、雙親結(jié)點或父結(jié)點：結(jié)點的前驅(qū)就是該結(jié)點的父結(jié)點
7、孩子結(jié)點或子結(jié)點：結(jié)點的后繼就是該結(jié)點的子結(jié)點
8、兄弟結(jié)點：具有相同父結(jié)點的結(jié)點互為兄弟結(jié)點
9、堂兄弟結(jié)點：父結(jié)點在同一層的結(jié)點互為堂兄弟結(jié)點
10、結(jié)點的祖先：從根結(jié)點到該結(jié)點一路上經(jīng)過的所有結(jié)點都是該結(jié)點的祖先，如：根結(jié)點是除自身外所有結(jié)點的祖先
11、子孫：該結(jié)點后面的所有結(jié)點都是該結(jié)點的子孫，如：除根結(jié)點外所有結(jié)點都是根結(jié)點的子孫
12、結(jié)點的層次：根為第1層，以此類推
13、深度：該結(jié)點的層次就是深度
14、樹的高度：樹中結(jié)點的最大層次就是樹的高度
15、森林：由m（m>=0）棵互不相交的樹組成的集合稱為森林，空樹也叫森林
3、樹的表示形式
樹可以有：雙親表示法，孩子表示法，孩子雙親表示法，孩子兄弟表示法等等
二、二叉樹
1、初識二叉樹
（1）二叉樹是樹
（2）二叉樹的每個根結(jié)點都只有兩棵子樹，分別為左子樹和右子樹
（3）二叉樹也可以是空樹
（4）二叉樹的度 <=2，所以二叉樹的結(jié)點個數(shù) = 度為0的結(jié)點個數(shù)+度為1的結(jié)點個數(shù)+度為2的結(jié)點個數(shù)
2、兩種特殊的二叉樹
（1）滿二叉樹
除葉子結(jié)點外，結(jié)點的度都為2，結(jié)點總數(shù)為：(2^k)-1，k為樹的高度
（2）完全二叉樹
從上到下，從左到右，中間不少結(jié)點。
滿二叉樹是特殊的完全二叉樹。
完全二叉樹中，度為1的結(jié)點個數(shù) 要么為0，要么為1 —— 結(jié)點總數(shù)是偶數(shù)時，度為1的結(jié)點個數(shù)為 1，結(jié)點總數(shù)是奇數(shù)時，度為1的結(jié)點個數(shù)為 0
3、二叉樹的性質(zhì)?
1、二叉樹的第 k 層，最多有 2^(k-1) 個結(jié)點（空樹除外）
2、深度為 k 的二叉樹，最多有(2^k)-1個結(jié)點
3、任意一棵二叉樹，葉子結(jié)點的個數(shù) 比 度為2的結(jié)點的個數(shù) 多 1
4、n個結(jié)點的完全二叉樹，深度k為：(2^k)?-1= n，k為 log以2為底n+1的對數(shù)，向上取整
5、完全二叉樹，
若父結(jié)點下標(biāo)為 i，則 左孩子下標(biāo)為：2^i+1，右孩子下標(biāo)為：2^i+2
若子結(jié)點下標(biāo)為 i，則父結(jié)點下標(biāo)為：i-1/2
題目：
1. 某二叉樹共有 399 個結(jié)點，其中有 199 個度為 2 的結(jié)點，則該二叉樹中的葉子結(jié)點數(shù)為（B、 200 ）199+1
2.在具有 2n 個結(jié)點的完全二叉樹中，葉子結(jié)點個數(shù)為（A、n）2n = n0+1+n0-1
3.一個具有767個節(jié)點的完全二叉樹，其葉子節(jié)點個數(shù)為（B、384）767 = n0+0+n0-1
4、二叉樹的遍歷
前序遍歷：根，左子樹，右子樹
中序遍歷：左子樹，根，右子樹
后序遍歷：左子樹，右子樹，根
層序遍歷：從上到下，從左到右
如：寫出下面這棵二叉樹的前序遍歷，中序遍歷，后序遍歷，層序遍歷的結(jié)果
前序遍歷：A B D E H C F G
中序遍歷：D B E H A F C G
后序遍歷：D H E B F G C A
層序遍歷：A B C D E F G H
題目：
1、設(shè)一課二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹前序遍歷序列為(D)
A: adbce B: decab C: debac D: abcde
后序遍歷，從后往前，每一個結(jié)點都是根結(jié)點。拿著根結(jié)點，去中序遍歷里看，根結(jié)點的左邊屬于左子樹的結(jié)點，根結(jié)點的右邊屬于右子樹的結(jié)點。
如，后序遍歷從后往前第一個結(jié)點就是整棵樹的根結(jié)點 a，然后看中序遍歷，則，b 屬于左子樹的結(jié)點，dce 屬于右子樹的結(jié)點。然后再看后序遍歷從后往前第二個結(jié)點，以此類推。
由此題引出兩個問題，
問題一：如果只給一個遍歷，能否創(chuàng)建一棵二叉樹？
不能。因為有可能存在兩棵不同的樹，某一個遍歷是一樣的。
問題二：如果只給前序遍歷和后序遍歷，能否創(chuàng)建一棵二叉樹？
不能。前序遍歷和后序遍歷都是只能確定根的位置，但不能確定左子樹或右子樹。
5、實現(xiàn)一棵二叉樹?
二叉樹的存儲結(jié)構(gòu)（物理結(jié)構(gòu)）有：順序存儲和鏈?zhǔn)酱鎯?/p>
這里我們使用孩子表示法來實現(xiàn)一個鏈?zhǔn)酱鎯Y(jié)構(gòu)的二叉樹。
1、前序遍歷 2、中序遍歷 3、后序遍歷 4、獲取樹中結(jié)點的個數(shù) 5、獲取葉子結(jié)點的個數(shù) 6、獲取第 k層 結(jié)點的個數(shù) 7、獲取二叉樹的高度 8、獲取第k層的所有結(jié)點：有點 帶返回值的前序遍歷 和 獲取第 k層 結(jié)點的個數(shù) 的結(jié)合版 9、找到值為value的元素 10、層序遍歷：和層序遍歷相關(guān)的想到用 隊列，用隊列會比較方便 11、判斷這棵樹是不是完全二叉樹：用 隊列
public class MyBinaryTree {
static class TreeNode{
public char val;
public TreeNode leftTree;//存儲左子樹的引用
public TreeNode rightTree;//存儲右子樹的引用
public TreeNode(char val){
this.val = val;
}
}
//創(chuàng)建一棵樹
public TreeNode createTree(){
TreeNode A = new TreeNode('A');
TreeNode B = new TreeNode('B');
TreeNode C = new TreeNode('C');
TreeNode D = new TreeNode('D');
TreeNode E = new TreeNode('E');
TreeNode F = new TreeNode('F');
TreeNode G = new TreeNode('G');
TreeNode H = new TreeNode('H');
A.leftTree = B;
A.rightTree = C;
B.leftTree = D;
B.rightTree = E;
C.leftTree = F;
C.rightTree = G;
E.rightTree = H;
return A;
}
//前序遍歷
public void preOrder(TreeNode root){
if(root == null){
return;
}
System.out.print(root.val+" ");
preOrder(root.leftTree);
preOrder(root.rightTree);
}
//帶返回值
public List<Character> preorderTraversal(TreeNode root) {
//子問題思路：先放根，然后放左子樹，然后放右子樹
List<Character> list = new ArrayList<>();
//遞歸的終止條件
if(root == null){
return list;
}
list.add(root.val);
list.addAll(preorderTraversal(root.leftTree));
list.addAll(preorderTraversal(root.rightTree));
return list;
}
//中序遍歷
public void inOrder(TreeNode root){
if(root == null){
return;
}
inOrder(root.leftTree);
System.out.print(root.val+" ");
inOrder(root.rightTree);
}
//后序遍歷
public void postOrder(TreeNode root){
if(root == null){
return;
}
postOrder(root.leftTree);
postOrder(root.rightTree);
System.out.print(root.val+" ");
}
//獲取樹中結(jié)點的個數(shù)
public int size(TreeNode root){
//左子樹結(jié)點的個數(shù)+右子樹結(jié)點的個數(shù)+1
//遞歸的終止條件
if(root == null){
return 0;
}
return size(root.leftTree)+size(root.rightTree)+1;
}
//獲取葉子結(jié)點的個數(shù)
public int getLeafNodeCount(TreeNode root){
//左子樹葉子結(jié)點的個數(shù)+右子樹葉子結(jié)點的個數(shù)
if(root == null){
return 0;
}
//滿足下面條件的就是葉子結(jié)點,遞歸的終止條件
if(root.leftTree == null && root.rightTree == null){
return 1;
}
return getLeafNodeCount(root.leftTree) + getLeafNodeCount(root.rightTree);
}
//獲取第 k層 結(jié)點的個數(shù)
public int getKLevelNodeCount(TreeNode root,int k){
//第k層結(jié)點的個數(shù) = 左子樹第k-1層結(jié)點的個數(shù)+右子樹第k-1層結(jié)點的個數(shù)
if(k <= 0){
throw new KWrongFulException("k不合法異常");
}
//如果k大于樹的高度，k還沒減到0，root先變成null，返回0
//下面兩個都算循環(huán)的終止條件
if(root == null){
return 0;
}
if(k == 1){
return 1;
}
return getKLevelNodeCount(root.leftTree,k-1)
+getKLevelNodeCount(root.rightTree,k-1);
}
//獲取二叉樹的高度
public int getHeight(TreeNode root){
//左子樹的高度，右子樹的高度的最大值 +1
if(root == null){
return 0;
}
int leftHeight = getHeight(root.leftTree);
int rightHeight = getHeight(root.rightTree);
return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
}
//獲取第 k 層的所有結(jié)點
//有點像 帶返回值的前序遍歷 和 獲取第 k層 結(jié)點的個數(shù) 的結(jié)合
public List<Character> KLevel(TreeNode root,int k){
List<Character> list = new LinkedList<>();
if(root == null){
return list;
}
//把 第 k 層的每一個結(jié)點都 add 進 list，返回給父結(jié)點
if(k == 1){
list.add(root.val);
return list;
}
//父結(jié)點接收到兩個子結(jié)點返回的 list，add到自己的list里
list.addAll(KLevel(root.leftTree,k-1));
list.addAll(KLevel(root.rightTree,k-1));
//然后返回給他的父結(jié)點，于是層層遞進，最后根結(jié)點的list里 放的就是 第k層 的所有結(jié)點
return list;
}
//找到值為value的元素
public TreeNode find(TreeNode root,char val){
//先找根，然后找左子樹，然后找右子樹，找到就返回，找不到返回null
//下面兩個都是遞歸的終止條件
if(root == null){
return null;
}
if(root.val == val){
return root;
}
TreeNode ret1 = find(root.leftTree,val);
//如果 ret1 里面不是空，說明找到了
//如果 ret1 里面是空，說明沒找到
if (ret1 != null){
return ret1;
}
TreeNode ret2 = find(root.rightTree,val);
if (ret2 != null){
return ret2;
}
return null;
}
//層序遍歷：用到隊列，先進先出
//層序遍歷不用遞歸比較方便，本來就是按順序（從上到下，從左到右）輸出的呀，
// 不像前序中序和后序遍歷，必須得遞歸
public void levelOrder(TreeNode root){
Queue<TreeNode> queue = new LinkedList<>();
if(root == null){
return;
}
queue.offer(root);
while(!queue.isEmpty()){
TreeNode ret = queue.poll();
System.out.print(ret+" ");
if(ret.leftTree != null){
queue.offer(ret.leftTree);
}
if(ret.leftTree != null){
queue.offer(ret.rightTree);
}
}
}
//有返回值的層序遍歷：用到隊列比較方便
//難點在如何確定每一層，這里我們用到了隊列中的size
//每一輪都要定義一個size
public List<List<Character>> levelOrderTraversal(TreeNode root){
List<List<Character>> tmp = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(root == null){
return tmp;
}
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Character> list = new ArrayList<>();
while(size > 0) {
TreeNode ret = queue.poll();
size--;
list.add(ret.val);
if (ret.leftTree != null) {
queue.offer(ret.leftTree);
}
if (ret.rightTree != null) {
queue.offer(ret.rightTree);
}
}
tmp.add(list);
}
return tmp;
}
//判斷這棵樹是不是完全二叉樹：用隊列
public boolean isCompleteTree(TreeNode root){
Queue<TreeNode> queue = new LinkedList<>();
if(root == null){
return true;
}
queue.offer(root);
while(!queue.isEmpty()){
TreeNode ret = queue.peek();
if(ret == null){
break;
}
queue.poll();
queue.offer(ret.leftTree);
queue.offer(ret.rightTree);
}
//走到這，隊列里要么都是null，要么除了null還有結(jié)點，后者說明不是完全二叉樹
while(!queue.isEmpty()){
TreeNode ret = queue.poll();
if(ret != null){
return false;
}
}
return true;
}
}
6、二叉樹題目（沒代碼的后面會給補上）
1、判斷兩棵樹相不相等 2、判斷其中一棵樹是不是另一棵樹的子樹 3、翻轉(zhuǎn)二叉樹 4、判斷是不是平衡二叉樹 5、判斷兩棵二叉樹是不是鏡像對稱 6、判斷是不是軸對稱二叉樹 7、二叉樹的層序遍歷 8、二叉樹的構(gòu)建和遍歷 9、給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先 10、二叉搜索樹轉(zhuǎn)換成排序雙向鏈表 11、二叉樹前序非遞歸遍歷實現(xiàn) 12、二叉樹中序非遞歸遍歷實現(xiàn) 13、二叉樹后序非遞歸遍歷實現(xiàn) 14、根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹 15、根據(jù)一棵樹的中序遍歷與后序遍歷構(gòu)造二叉樹 16、二叉樹創(chuàng)建字符串
（1）判斷兩棵樹是否相同 鏈接
//時間復(fù)雜度：O(min(m,n))，其中 m和n 分別是兩個二叉樹的結(jié)點數(shù)
public boolean isSameTree(TreeNode p, TreeNode q) {
//先判斷根一樣不，再判斷左子樹一樣不，再判斷右子樹一樣不，只有全一樣(結(jié)構(gòu)和值都一樣)，才返回true
//如果都是空樹
if(p == null && q == null){
return true;
}
//如果一個是空樹，一個不是
if((p == null && q != null) || (p != null && q == null)){
return false;
}
//走到這，則兩個都不是空樹
//值不相等
if(p.val != q.val){
return false;
}
//走到這，既不是空樹，根的值也相等
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}（2）判斷其中一棵樹是不是另一棵樹的子樹 鏈接?
/**
* 2、判斷其中一棵樹是不是另一棵樹的子樹
* 時間復(fù)雜度：O(m*n)，其中 m和n 分別是兩個二叉樹的結(jié)點數(shù)
*/
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//題目中已經(jīng)給出了：兩棵樹都不是空樹
//如果一直沒有匹配，root就會一直root.left，root會為空
if(root == null || subRoot == null){
return false;
}
//先判斷subRoot是否和root相等，
if(isSameTree(root,subRoot)) return true;
//再判斷subRoot是否是root的左子樹的子樹
if(isSubtree(root.left,subRoot)) return true;
//再判斷subroot是否是root的右子樹的子樹
if(isSubtree(root.right,subRoot)) return true;
return false;
}
public boolean isSameTree(TreeNode p, TreeNode q) {
//先判斷根一樣不，再判斷左子樹一樣不，再判斷右子樹一樣不，只有全一樣(結(jié)構(gòu)和值都一樣)，才返回true
//如果都是空樹
if(p == null && q == null){
return true;
}
//如果一個是空樹，一個不是
if((p == null && q != null) || (p != null && q == null)){
return false;
}
//走到這，則兩個都不是空樹
//值不相等
if(p.val != q.val){
return false;
}
//走到這，既不是空樹，根的值也相等
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}（3）翻轉(zhuǎn)二叉樹 鏈接
public TreeNode invertTree(TreeNode root) {
//先翻轉(zhuǎn)根結(jié)點的左子樹和右子樹，再翻轉(zhuǎn)左子樹的左子樹和右子樹，再翻轉(zhuǎn)右子樹的左子樹和右子樹
if(root == null){
return null;
}
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}（4）判斷是不是平衡二叉樹 鏈接
//判斷是不是平衡二叉樹，時間復(fù)雜度O(n)
public boolean isBalanced(TreeNode root) {
//平衡二叉樹：每棵子樹的高度差都要 <=1
if(root == null){
return true;
}
int ret = height(root);
if(ret == -1){
return false;
}
return true;
}
//求二叉樹的高度，時間復(fù)雜度是O(n)
//求根結(jié)點高度的時候，其實已經(jīng)求了所有結(jié)點的高度，如果發(fā)現(xiàn)左樹右樹高度差大于1，說明已經(jīng)不平衡了，就返回-1
//否則就返回左樹右樹高度最大值+1
//所以，我們需要在每次獲得左樹和右樹高度的時候，都接收判斷一下，如果發(fā)現(xiàn)接收到的是-1，說明已經(jīng)出現(xiàn)了不平衡
//如果一直沒有接收到-1，說明這個二叉樹的每棵子樹都是平衡的，所以這棵二叉樹是高度平衡的二叉樹。
//求二叉樹的高度
public int height(TreeNode root){
if(root == null){
return 0;
}
//求左子樹的高度
int leftH = height(root.left);
if(leftH == -1){
return -1;
}
//求右子樹的高度
int rightH = height(root.right);
if(rightH == -1){
return -1;
}
//如果左右子樹的高度差 <= 1，返回左右子樹高度的最大值+1
//如果左右子樹的高度差 > 1，返回-1，說明已經(jīng)出現(xiàn)不平衡了
if(Math.abs(leftH - rightH) <= 1){
return Math.max(leftH,rightH) + 1;
}else{
return -1;
}
}（5）判斷兩棵樹是不是鏡像對稱
public boolean isMirrorSymmetry(TreeNode leftTree,TreeNode rightTree){
//如果兩個都是空樹
if(leftTree == null && rightTree == null){
return true;
}
//如果一個是空樹一個不是
if((leftTree == null && rightTree != null) || (leftTree != null && rightTree == null)){
return false;
}
//到這，兩個都不是空樹
if(leftTree.val != rightTree.val){
return false;
}
//到這，兩個都不是空樹，且根的值相同
return isMirrorSymmetry(leftTree.left,rightTree.right) &&
isMirrorSymmetry(leftTree.right,rightTree.left);
}（6）判斷是不是軸對稱二叉樹 鏈接
public boolean isSymmetric(TreeNode root) {
if(root == null){
return true;
}
//從第二層開始，比較左子樹和右子樹是否是鏡像的
return isMirrorSymmetry(root.left,root.right);
}
//先比較根是否是鏡像的，再比較子樹是否是鏡像的
public boolean isMirrorSymmetry(TreeNode leftTree,TreeNode rightTree){
//如果兩個都是空樹
if(leftTree == null && rightTree == null){
return true;
}
//如果一個是空樹一個不是
if((leftTree == null && rightTree != null) || (leftTree != null && rightTree == null)){
return false;
}
//到這，兩個都不是空樹
if(leftTree.val != rightTree.val){
return false;
}
//到這，兩個都不是空樹，且根的值相同
return isMirrorSymmetry(leftTree.left,rightTree.right) &&
isMirrorSymmetry(leftTree.right,rightTree.left);
}（7）二叉樹的層序遍歷?鏈接
//有返回值的層序遍歷：用到隊列比較方便
//難點在如何確定每一層，這里我們用到了隊列中的size
//每一輪都要定義一個size
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> tmp = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(root == null){
return tmp;
}
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> list = new ArrayList<>();
while(size > 0) {
TreeNode ret = queue.poll();
size--;
list.add(ret.val);
if (ret.left != null) {
queue.offer(ret.left);
}
if (ret.right != null) {
queue.offer(ret.right);
}
}
tmp.add(list);
}
return tmp;
}（8）二叉樹的構(gòu)建和遍歷?鏈接
public class Main {
static class TreeNode{
public char val;
public TreeNode leftTree;//存儲左子樹的引用
public TreeNode rightTree;//存儲右子樹的引用
public TreeNode(char val){
this.val = val;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextLine()) {
String str = scanner.nextLine();//str里存的就是讀入的字符串
//首先遍歷字符串，拿到字符串中的每個元素，
//并創(chuàng)建結(jié)點，通過前序遍歷構(gòu)造一棵二叉樹
TreeNode root = createTree(str);
//然后再中序遍歷輸出
inOrder(root);
}
}
//通過前序遍歷構(gòu)造二叉樹
public static int i = 0;
public static TreeNode createTree(String str){
TreeNode root = null;
//通過i拿到字符串中的每個字符
char ch = str.charAt(i);
i++;
if(ch == '#'){
return null;
}
//把拿到的元素創(chuàng)建成結(jié)點
root = new TreeNode(ch);
root.leftTree = createTree(str);
root.rightTree = createTree(str);
return root;
}
//中序遍歷輸出
public static void inOrder(TreeNode root){
if(root == null){
return;
}
inOrder(root.leftTree);
System.out.print(root.val+" ");
inOrder(root.rightTree);
}
}（9）給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先 ?鏈接
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){
return null;
}
// p 和 q 其中有一個是root
if(p == root || q == root){
return root;
}
// p 和 q 分別在 root 的兩側(cè)
// p 和 q 都在 root 的左側(cè) 或 root 的右側(cè)
TreeNode ret1 = lowestCommonAncestor(root.left,p,q);
TreeNode ret2 = lowestCommonAncestor(root.right,p,q);
if(ret1 != null && ret2 != null){
return root;
}else if(ret1 != null){
return ret1;
}else if(ret2 != null){
return ret2;
}else{
return null;
}
}（10）二叉搜索樹轉(zhuǎn)換成排序雙向鏈表 鏈接
public TreeNode convert(TreeNode pRootOfTree) {
//二叉搜索樹：根左邊的比根小，根右邊的比根大
//中序遍歷二叉搜索樹是有序的，是從小到大的
//所以，轉(zhuǎn)換成排序的雙向鏈表，采用中序遍歷的方法
if(pRootOfTree == null){
return null;
}
convertChild(pRootOfTree);
TreeNode head = pRootOfTree;
//鏈表的頭就是二叉搜素樹最左邊的那個結(jié)點
while(head.left != null){
head = head.left;
}
return head;
}
public TreeNode prev = null;
public void convertChild(TreeNode pRoot){
if(pRoot == null){
return;
}
convertChild(pRoot.left);
if(prev != null){
prev.right = pRoot;
}
pRoot.left = prev;
prev = pRoot;
convertChild(pRoot.right);
}（11）二叉樹前序非遞歸遍歷實現(xiàn) 鏈接
public TreeNode cur = null;
public List<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
//用到棧
//前序遍歷：根，左，右。往左走，一直入棧，只有這個節(jié)點沒用了，才能出棧。
if(root == null){
return list;
}
cur = root;
while(cur != null || !stack.empty()){
while(cur != null){
stack.push(cur);
list.add(cur.val);
cur = cur.left;
}
//cur 等于空，說明cur的左走完了，此時棧頂元素就是cur
//根和左走完了，此時才能彈出棧頂元素（因為直到這時棧頂元素才沒用了）
cur = stack.pop();
cur = cur.right;
}
return list;
}（12）二叉樹中序非遞歸遍歷實現(xiàn) 鏈接
（13）二叉樹后序非遞歸遍歷實現(xiàn) 鏈接
（14）根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹 鏈接
（15）根據(jù)一棵樹的中序遍歷與后序遍歷構(gòu)造二叉樹 鏈接文章來源：http://www.zghlxwxcb.cn/news/detail-845330.html
（16）二叉樹創(chuàng)建字符串 鏈接文章來源地址http://www.zghlxwxcb.cn/news/detail-845330.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】—— 二叉樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
