文章目錄

1. 樹型結構
- 1.1 概念
- 1.2 要掌握的知識點
- 1.3 樹的存盤形式
- 1.4 樹的應用
2. 二叉樹
- 2.1 概念
- 2.2 二叉樹的基本形態
- 2.3 兩種特殊的二叉樹
- - 2.3.1 滿二叉樹
  - 2.3.2 完全二叉樹
- 2.4 二叉樹的性質
- 2.5 二叉樹的存盤
- 2.6 二叉樹的基本操作
- - 2.6.1 二叉樹的前、中、后序遍歷（遞回實作）
  - 2.6.2 二叉樹的層序遍歷
  - 2.6.2 二叉樹的實作
- 2.7 前中后序的非遞回實作
3. 二叉樹練習題
- 3.1 二叉樹基礎練習題
- - 3.1.1 二叉樹的前序遍歷
  - 3.1.2 二叉樹的中序遍歷
  - 3.1.3 二叉樹的后序遍歷
  - 3.1.4 相同的樹
  - 3.1.5 另一棵樹的子樹
  - 3.1.6 二叉樹的最大深度
  - 3.1.7 平衡二叉樹
  - 3.1.8 對稱二叉樹
- 3.2 二叉樹進階練習題
- - 3.2.1 二叉樹的構建及遍歷
  - 3.2.2 二叉樹的層序遍歷
  - 3.2.3 二叉樹的最近公共祖先
  - 3.2.4 二叉搜索樹與雙向鏈表
  - 3.2.5 從前序與中序遍歷序列構造二叉樹
  - 3.2.6 從中序與后序遍歷序列構造二叉樹
  - 3.2.7 根據二叉樹創建字串

1. 樹型結構

1.1 概念

樹：是一種非線性的資料結構，它是由 n（n>=0）個有限節點組成的一個具有層次關系的集合，把它叫做樹是因為它看起來像一顆倒掛的樹，它是根朝上，葉朝下，

在這里插入圖片描述

特點：

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

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

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

樹是遞回定義的

注意：

子樹是不相交的，即除每個節點有且僅有一個父節點，而下面的幾種情況都是非樹

情況一：
情況二：
情況三：

1.2 要掌握的知識點

大家可以配合此圖，食用以下關于樹的知識點在這里插入圖片描述

節點的度： 一個節點含有的子樹的個數稱為該節點的度，如上圖，T 節點的度為4
樹的度： 一顆樹中，最大的節點的度稱為樹的度，如上圖，該樹的度為4
葉子節點或終端節點： 度為0的節點稱為葉子節點，如上圖，T4、T11、T21、T22、T31、T32、T33為葉子節點
雙親節點或父節點： 若一個節點含有子節點，則這個節點稱為其子節點的父節點，如上圖，T 節點是 T4 節點的父節點
孩子節點或子節點： 一個節點含有的子樹的根節點稱為該節點的子節點，如上圖，T4 節點是 T 節點的子節點
根節點： 一顆樹中，沒有雙親節點的節點稱為根節點，如上圖，T 節點為根節點
節點的層次： 從根開始定義，根為第1層，根的子節點為第二層，以此類推，如上圖，該樹有3層
節點的深度： 某節點層次是第幾層，則它的深度是多少，如上圖，T 節點深度為1，T1 節點深度為2
樹的高度： 樹中節點的最大層次，如上圖，樹的高度為3
非終端節點或分支節點： 度不為0的節點，如上圖，T、T1、T2、T3 為分支節點
兄弟節點： 父親節點相同的節點互稱為兄弟節點，如上圖，T1、T2、T3、T4 互稱為兄弟節點
堂兄弟節點： 雙親在同一層次的節點互稱為堂兄弟節點，如上圖，T11、T21 互稱為堂兄弟節點
節點的祖先： 從根節點到該節點所經過分支上的所有節點都稱為該節點的祖先，如上圖，T、T1 節點都為 T11 節點的祖先
子孫： 以某節點為根的子樹中，任意節點都稱為該節點的子孫，如上圖，該樹中除 T 節點其它節點都是 T 節點的子孫
森林： 由 m（m>=0）棵互不相交的樹的集合稱為森林，

1.3 樹的存盤形式

樹是一種非線性的資料結構，所以存盤資料相較于線性結構其實要麻煩很多，常用的方法有：雙親表示法、孩子表示法、孩子兄弟表示法等等，這里我們主要介紹最常用的孩子兄弟表示法，

孩子兄弟表示法的代碼表現形式：

class Node{
    int val;			// 樹中存盤的資料
    Node firstChild;	// 第一個孩子的參考
    Node nextBrother;	// 下一個兄弟的參考
}

我們可以參考下面這棵樹的圖片，對它進行決議來理解上述代碼的意思在這里插入圖片描述

決議： 每一個節點都有一個第一個孩子結點和下一個兄弟結點，通過這兩個結點，就可以將這棵樹的所有結點聯系起來，使得我們可以遍歷，并將資料存盤，

在這里插入圖片描述

1.4 樹的應用

其實我們電腦的檔案系統管理和樹的結構很相似，尤其是有著一切皆檔案之稱的 linux 系統，在這里插入圖片描述

因此我們可以使用樹的知識，去構建一個系統的目錄和檔案，

2. 二叉樹

2.1 概念

二叉樹：是 n 個有限元素的集合，該集合或者為空，或者是由一個根節點加上兩棵不相交的，被分別稱為左子樹和右子樹的二叉樹組成，

在這里插入圖片描述

特點：

當集合為空時，該二叉樹稱為空二叉樹，
在二叉樹中，一個元素也稱為一個結點，
每個結點最多有兩棵子樹，即二叉樹不存在度大于2的結點，
二叉樹的子樹有左右之分，其次子樹的次序不能顛倒，因此二叉樹是有序樹，

2.2 二叉樹的基本形態

一般二叉樹都是由以下四種形態的二叉樹組合形成的在這里插入圖片描述

注意：

子樹也必須是二叉樹才能滿足該樹整體是一個二叉樹

2.3 兩種特殊的二叉樹

2.3.1 滿二叉樹

滿二叉樹： 一個二叉樹，如果每一層的節點數都達到最大值，則這個二叉樹就是滿二叉樹，

性質： 如果一個二叉樹的層數是k，且節點數是 2^k-1，則它就是滿二叉樹，

在這里插入圖片描述

2.3.2 完全二叉樹

完全二叉樹： 完全二叉樹是效率很高的資料結構，它是由滿二叉樹引申出來的，它的葉子節點只會出現在最后2層，且最后一層的葉子節點都靠左對齊，（滿二叉樹是一種特殊的完全二叉樹）

在這里插入圖片描述

2.4 二叉樹的性質

若規定根節點的層數為1，則一棵非空二叉樹的第 i 層上最多有 2^i-1（i>0）個節點
若規定只有根節點的二叉樹的深度為1，則深度為 k 的二叉樹的最大節點數是 2^k-1（k>=0）
對任何一棵二叉樹，如果其葉子節點個數為 m，度為2的非葉子節點個數為 n，則有 m=n+1
具有 n 個節點的完全二叉樹的深度為 log₂(n+1) 向上取整
對于具有 n 個節點的完全二叉樹，如果按照從上至下、從左至右的順序對所有節點從0開始編號，則對序號為 i 的節點有：
若 i>0，雙親序號為：(i-1)/2
若 i=0，i 為根節點編號，無雙親節點
若 2i+1<n，左孩子序號為：2i+1，否則沒有左孩子
若 2i+2<n，右孩子序號為：2i+2，否則沒有右孩子

練習題：

假設一棵完全二叉樹中總共有1000個節點，則該二叉樹中有____個葉子節點，____個非葉子節點，____個節點只有左孩子，____個節點只有右孩子，

答案：

500、500、1、0

決議：

由于這是一個完全二叉樹，所以不可能出現只有右孩子的節點，故最后一空為0
通過節點個數1000，可以推匯出該樹的深度為10
第10層節點數可以通過總節點數減去前9層節點數得到，為1000-511=489
葉子節點數=第10層的節點數+第九層度為0的節點數，而通過第10層的節點數可以知道他們的父節點有489/2+1=245
由于這是一個完全二叉樹，所以第9層的節點肯定是滿的，易得第9層節點數為256，而去除第九層度不為0的節點數，得到第九層葉子節點有256-245=11
故葉子節點數為489+11=500，非葉子節點數為1000-500=500
而完全二叉樹的節點只有左子樹的結果有1或0，通過第十層的節點數489為偶數，我們知道肯定有一個父節點只有一個孩子節點，即只有左子樹的節點為1

2.5 二叉樹的存盤

二叉樹的存盤結構分為：順序存盤（在堆中介紹）和類似于鏈表的鏈式存盤

二叉樹的鏈式存盤是通過一個一個的節點參考起來的，表示方法有：孩子表示法和孩子雙親表示法

孩子表示法：

class Node{
    int val;		// 數值域
    Node left;		// 左孩子的參考，常常代表以左孩子為根的整棵樹
    Node right;		// 右孩子的參考，常常代表以右孩子為根的整棵樹
}

孩子雙親表示法：

class Node{
    int val;		// 數值域
    Node left;		// 左孩子的參考，常常代表以左孩子為根的整棵樹
    Node right;		// 右孩子的參考，常常代表以右孩子為根的整棵樹
    Node parent;	// 當前節點的根節點
}

2.6 二叉樹的基本操作

2.6.1 二叉樹的前、中、后序遍歷（遞回實作）

二叉樹是一個非線性的資料結構，對它進行遍歷的方式其實有多種，因此如果我們都以自己的方式去遍歷二叉樹，那么這個代碼的易懂性就大大降低，顯得很混亂，

為此對于二叉樹，根據遍歷根節點的先后次序，我們有以下三種遍歷方式（N：代表根節點；L：代表根節點的左子樹；R：代表根節點的右子樹）

前序遍歷（NLR）： 先訪問根節點?根的左子樹?根的右子樹
中序遍歷（LNR）： 先訪問根的左子樹?根節點?根的右子樹
后序遍歷（LRN）： 先訪問根的左子樹?根的右子樹?根節點

練習題：

請寫出下面這棵二叉樹的四種遍歷方式

答案：

前序遍歷：ABDEHCFG
中序遍歷：DBEHAFCG
后序遍歷：DHEBFGCA

注意：

不管是前序、中序還是后序遍歷，遍歷的路徑是一樣的，但訪問的方式是不一樣的

2.6.2 二叉樹的層序遍歷

除了前中后序遍歷外，二叉樹還有一種很直觀的遍歷方式：層序遍歷，層序遍歷就是從二叉樹的根節點出發，首先訪問該樹的第一層的根節點，然后從左到右訪問第二層的節點，接著是第三層的節點，以此類推，

在這里插入圖片描述

對于上圖的樹，使用層序遍歷，節點被訪問的順序為：ABCDEFGH

層序遍歷一般使用非遞回的方式，具體的實作方法可以使用佇列，在這里插入圖片描述

代碼： 實作層序遍歷

public void levelOrderTraversal(Node root){
    if(root==null){
        return;
    }
    Queue<Node> queue=new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        Node node=queue.poll();
        System.out.print(node.val+" ");
        if(node.left!=null) {
            queue.offer(node.left);
        }
        if(node.right!=null) {
            queue.offer(node.right);
        }
    }
}

相關習題：

習題一： 求一棵樹的左視圖

代碼：

public List<Character> leftMap(Node root) {
    List<Character> ret=new ArrayList<>();
    if(root==null){
        return ret;
    }
    Queue<Node> queue =new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        int size=queue.size();
        int count=size;
        while(size>0){
            Node top=queue.poll();
            if(count==size){
                ret.add(top.val);
            }
            if(top.left!=null){
                queue.offer(top.left);
            }
            if(top.right!=null){
                queue.offer(top.right);
            }
            size--;
        }
    }
    return ret;
}

習題二： 求二叉樹的最大寬度

代碼：

public int maxWidth(Node root) {
    if(root==null){
        return 0;
    }
    Queue<Node> queue =new LinkedList<>();
    queue.offer(root);
    int max=0;
    while(!queue.isEmpty()){
        int size=queue.size();
        max=Math.max(max,size);
        while(size>0){
            Node top=queue.poll();
            if(top.left!=null){
                queue.offer(top.left);
            }
            if(top.right!=null){
                queue.offer(top.right);
            }
            size--;
        }
    }
    return max;
}

習題三： 判斷一棵樹是不是完全二叉樹

代碼：

public boolean isCompleteTree(Node root){
    if(root==null){
        return true;
    }
    Queue<Node> queue=new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        Node top=queue.poll();
        if(top==null){
            break;
        }
        queue.offer(top.left);
        queue.offer(top.right);
    }
    while(!queue.isEmpty()){
        Node top=queue.peek();
        if(top!=null){
            return false;
        }
        queue.poll();
    }
    return true;
}

2.6.2 二叉樹的實作

由于二叉樹的創建一般使用遞回，而遞回創建二叉樹將在后面重點介紹，故這里使用窮舉法來創建下面這棵二叉樹在這里插入圖片描述

實作代碼：

class Node{
    public char val;
    public Node left;
    public Node right;
    public Node(char val){
        this.val=val;
    }
}
public class TestBinaryTree {

    // 使用窮舉的方式創建一棵二叉樹
    public Node createTree(){
        Node A=new Node('A');
        Node B=new Node('B');
        Node C=new Node('C');
        Node D=new Node('D');
        Node E=new Node('E');
        Node F=new Node('F');
        Node G=new Node('G');
        Node H=new Node('H');
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        E.right=H;
        C.left=F;
        C.right=G;
        return A;
    }

    // 前序遍歷
    public void preOrderTraversal(Node root){
        if(root==null) {
            return;
        }
        System.out.print(root.val+" ");
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);

    }

    // 中序遍歷
    public void inOrderTraversal(Node root) {
        if (root == null) {
            return;
        }
        inOrderTraversal(root.left);
        System.out.print(root.val+" ");
        inOrderTraversal(root.right);
    }

    // 后序遍歷
    public void posOrderTraversal(Node root){
        if(root==null){
            return;
        }
        posOrderTraversal(root.left);
        posOrderTraversal(root.right);
        System.out.print(root.val+" ");
    }

    // 遍歷思路-求節點個數
    public static int size=0;
    public void getSize1(Node root){
        if(root==null){
            return;
        }
        size++;
        getSize1(root.left);
        getSize1(root.right);
    }

    // 子問題思路-求節點個數
    public int getSize2(Node root){
        if(root==null){
            return size;
        }
        int val=1+getSize2(root.left)+getSize2(root.right);
        return val;
    }

    // 遍歷思路-求葉子節點個數
    public static int leafSize;
    public void getLeafSize1(Node root){
        if(root==null){
            return;
        }
        if(root.left==null&&root.right==null){
            leafSize++;
            return;
        }
        getLeafSize1(root.left);
        getLeafSize1(root.right);
    }

    // 子問題思路-求葉子節點個數
    public int getLeafSize2(Node root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null) {
            return 1;
        }
        int val=getLeafSize2(root.left)+getLeafSize2(root.right);
        return val;
    }

    // 第 k 層的節點個數
    public int getKLeafSize(Node root,int k){
        if(root==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        int val=getKLeafSize(root.left,k-1)+getKLeafSize(root.right, k-1);
        return val;
    }

    // 獲取當前二叉樹的高度
    public int getHeight(Node root){
        if(root==null){
            return 0;
        }
        return 1+Math.max(getHeight(root.left),getHeight(root.right));
    }

    // 查找二叉樹的某個節點
    public Node find(Node root,char val){
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }
        Node leftNode=find(root.left,val);
        if(leftNode.val==val){
            return leftNode;
        }
        Node rightNode=find(root.right,val);
        if(rightNode.val==val){
            return rightNode;
        }
        return null;
    }
}

2.7 前中后序的非遞回實作

遞回的實作都是在堆疊上進行的，如果我們要用非遞回的方式實作一棵二叉樹，那么我們的核心思想就是創建一個堆疊，并在這個堆疊上模擬遞回，

前序遍歷非遞回實作

代碼示例：

public void preOrderTraversal(Node root){
    if(root==null){
        return;
    }
    Stack<Node> stack=new Stack<>();
    Node cur=root;
    while(cur!=null||!stack.empty()){
        while(cur!=null){
            stack.push(cur);
            System.out.print(cur.val+" ");
            cur=cur.left;
        }
        Node top=stack.pop();
        cur=top.right;
    }
}

中序遍歷非遞回實作

代碼示例：

public void inOrderTraversal(Node root){
    if(root==null){
        return;
    }
    Stack<Node> stack=new Stack<>(); 
    Node cur=root;
    while(cur!=null||!stack.empty()){
        while(cur!=null){
            stack.push(cur);
            cur=cur.left
        }
        Node top=stack.pop();
        System.out.print(top.val+" ");
        cur=top.right;
    }
}

后序遍歷非遞回實作

代碼示例：

public void posOrderTraversal(Node root){
    if(root==null){
        return;
    }
    Node prev=null;
    Stack<Node> stack=new Stack<>();
    Node cur=root;
    while(cur!=null||!stack.empty()){
        while(cur!=null){
            stack.push(cur);
            cur=cur.left;
        }
        Node top=stack.peek();
        cur=top.right;
        if(cur==null||cur.val==prev.val){
            System.out.print(top.val+" ");
            prev=stack.pop();
            cur=null;
        }
    }
}

3. 二叉樹練習題

3.1 二叉樹基礎練習題

3.1.1 二叉樹的前序遍歷

題目（OJ 鏈接）：

給你二叉樹的根節點 root ，回傳它節點值的前序遍歷，

代碼一： 子問題的思路：將左子樹、右子樹和根都存放進去

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list=new ArrayList<>();
    if(root==null){
        return 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;
}

代碼二： 遍歷思路：將每個節點都遍歷一遍

List<Integer> list=new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
    if(root==null){
        return list;
    }
    list.add(root.val);
    preorderTraversal(root.left);
    preorderTraversal(root.right);
    return list;
}

3.1.2 二叉樹的中序遍歷

題目（OJ 鏈接）：

給定一個二叉樹的根節點 root ，回傳它的中序遍歷，

代碼一： 子問題思路

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list=new ArrayList<>();
    if(root==null){
        return 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;
}

代碼二： 遍歷思路

List<Integer> list=new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
	if(root==null){
		return list;
	}
	inorderTraversal(root.left);
	list.add(root.val);
	inorderTraversal(root.right);
	return list;
}

3.1.3 二叉樹的后序遍歷

題目（OJ 鏈接）：

給定一個二叉樹，回傳它的后序遍歷，

代碼一： 子問題思

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list=new ArrayList<>();
    if(root==null){
        return 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;
}

代碼二： 遍歷思路

List<Integer> list=new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
	if(root==null){
		return list;
	}
	postorderTraversal(root.left);
	postorderTraversal(root.right);
	list.add(root.val);
	return list;
}

3.1.4 相同的樹

題目（OJ 鏈接）：

給你兩棵二叉樹的根節點 p 和 q ，撰寫一個函式來檢驗這兩棵樹是否相同，

如果兩個樹在結構上相同，并且節點具有相同的值，則認為它們是相同的，

代碼：

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);
    }
}

3.1.5 另一棵樹的子樹

題目（OJ 鏈接）：

給你兩棵二叉樹 root 和 subRoot ，檢驗 root 中是否包含和 subRoot 具有相同結構和節點值的子樹，如果存在，回傳 true ；否則，回傳 false ，

二叉樹 tree 的一棵子樹包括 tree 的某個節點和這個節點的所有后代節點，tree 也可以看做它自身的一棵子樹，

代碼：

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){
            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.1.6 二叉樹的最大深度

題目（OJ 鏈接）：

給定一個二叉樹，找出其最大深度，

代碼：

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
    }
}

3.1.7 平衡二叉樹

題目（OJ 鏈接）：

給定一個二叉樹，判斷它是否是高度平衡的二叉樹，

代碼一： 時間復雜度為 O(N²)

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
    }

    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        int leftDepth=maxDepth(root.left);
        int rightDepth=maxDepth(root.right);
        if(Math.abs(leftDepth-rightDepth)>1){
            return false;
        }
        return isBalanced(root.left)&&isBalanced(root.right);
    }
}

代碼二： 時間復雜度為 O(N)

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftDepth=maxDepth(root.left);
        int rightDepth=maxDepth(root.right);
        if(leftDepth>=0&&rightDepth>=0&&Math.abs(leftDepth-rightDepth)<=1){
            return 1+Math.max(leftDepth,rightDepth);
        }else{
            return -1;
        }
    }
    public boolean isBalanced(TreeNode root) {
        return maxDepth(root)>=0;
    }
}

3.1.8 對稱二叉樹

題目（OJ 鏈接）：

給定一個二叉樹，檢查它是否是鏡像對稱的，

代碼：

class Solution {
    public boolean isSymmetricChild(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 isSymmetricChild(leftTree.left,rightTree.right)&&isSymmetricChild(leftTree.right,rightTree.left);
    }

    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return false;
        }
        return isSymmetricChild(root.left,root.right);
    }
}

3.2 二叉樹進階練習題

3.2.1 二叉樹的構建及遍歷

題目（OJ 鏈接）：

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

代碼：

class TreeNode{
    public char val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(char val){
        this.val=val;
    }
}

public class Main{
    public static int i=0;
    public static TreeNode createBinaryTree(String str){
        if(str.length()==0){
            return null;
        }
        TreeNode root=null;
        if(str.charAt(i)=='#'){
            i++;
        }else{
            root=new TreeNode(str.charAt(i));
            i++;
            root.left=createBinaryTree(str);
            root.right=createBinaryTree(str);
        }
        return root;
    }
    
    public static void inOrderTraversal(TreeNode root){
        if(root==null){
            return;
        }
        inOrderTraversal(root.left);
        System.out.print(root.val+" ");
        inOrderTraversal(root.right);
    }
    
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        while(scan.hasNext()){
            String str=scan.nextLine();
            TreeNode ret=createBinaryTree(str);
            inOrderTraversal(ret);
            System.out.println();
        }
        
    }
}

3.2.2 二叉樹的層序遍歷

題目（OJ 鏈接）：

給你一個二叉樹，請你回傳其按 層序遍歷 得到的節點值，（即逐層地，從左到右訪問所有節點），

代碼：

class Solution {
    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()){
            int size=queue.size();
            List<Integer> list=new ArrayList<>();
            while(size>0){
                TreeNode top=queue.poll();
                list.add(top.val);
                if(top.left!=null){
                    queue.offer(top.left);
                }
                if(top.right!=null){
                    queue.offer(top.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }
}

3.2.3 二叉樹的最近公共祖先

題目（OJ 鏈接）：

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

百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個節點 p、q，最近公共祖先表示為一個節點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先），”

代碼：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        if(root==p||root==q){
            return root;
        }
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        if(left!=null&&right==null){
            return left;
        }
        if(left==null&&right!=null){
            return right;
        }
        if(left==null&&right==null){
            return null;
        }
        return root;
    }
}

3.2.4 二叉搜索樹與雙向鏈表

題目（OJ 鏈接）：

輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表，

代碼：

public class Solution {
    public TreeNode prev;
    public void ConvertChild(TreeNode pCur) {
        if(pCur==null){
            return;
        }
        ConvertChild(pCur.left);
        pCur.left=prev;
        if(prev!=null){
            prev.right=pCur;
        }
        prev=pCur;
        ConvertChild(pCur.right);
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){
            return null;
        }
        ConvertChild(pRootOfTree);
        TreeNode head=pRootOfTree;
        while(head.left!=null){
            head=head.left;
        }
        return head;
    }
}

補充：

二叉搜索樹特點： 左孩子比根節點小，右孩子比根節點大

3.2.5 從前序與中序遍歷序列構造二叉樹

題目（OJ 鏈接）：

給定一棵樹的前序遍歷 preorder 與中序遍歷 inorder，請構造二叉樹并回傳其根節點，

代碼：

class Solution {
    public int prevIndex=0;
    public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inBegin, int inEnd) {
        if(inBegin>inEnd){
            return null;
        }
        TreeNode root=new TreeNode(preorder[prevIndex]);

        int index=findIndex(inorder,inBegin,inEnd,root.val);
        prevIndex++;
        root.left=buildTreeChild(preorder,inorder,inBegin,index-1);
        root.right=buildTreeChild(preorder,inorder,index+1,inEnd);
        return root;    
    }
    public int findIndex(int[] inorder,int inBegin,int inEnd,int k){
        for(int i=inBegin;i<=inEnd;i++){
            if(k==inorder[i]){
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder==null||inorder==null){
            return null;
        }
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
}

3.2.6 從中序與后序遍歷序列構造二叉樹

題目（OJ 鏈接）：

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

代碼：

class Solution {
    public int rear;
    public TreeNode buildTreeChild(int[] inorder, int inBegin, int inEnd, int[] postorder) {
        if(inBegin>inEnd){
            return null;
        }
        TreeNode root=new TreeNode(postorder[rear]);
        int index=findIndex(inorder,inBegin,inEnd,postorder[rear]);
        rear--;
        root.right=buildTreeChild(inorder,index+1,inEnd,postorder);
        root.left=buildTreeChild(inorder,inBegin,index-1,postorder);
        return root;
    }
    public int findIndex(int[] inorder,int inBegin, int inEnd, int k){
        for(int i=inBegin;i<=inEnd;i++){
            if(inorder[i]==k){
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        rear=postorder.length-1;
        return buildTreeChild(inorder,0,inorder.length-1,postorder);
    }
}

3.2.7 根據二叉樹創建字串

題目（OJ 鏈接）：

你需要采用前序遍歷的方式，將一個二叉樹轉換成一個由括號和整陣列成的字串，

空節點則用一對空括號 “()” 表示，而且你需要省略所有不影響字串與原始二叉樹之間的一對一映射關系的空括號對，

代碼：

class Solution {
    public void tree2strChild(TreeNode root,StringBuilder sb){
        if(root==null){
            return;
        }
        sb.append(""+root.val);
        if(root.left==null){
            if(root.right==null){
                return;
            }else{
                sb.append("()");
            }
        }else{
            sb.append("(");
            tree2strChild(root.left,sb);
            sb.append(")");
        }
        if(root.right==null){
            return;
            
        }else{
            sb.append("(");
            tree2strChild(root.right,sb);
            sb.append(")");
        }
    }
    public String tree2str(TreeNode root) {
        if(root==null){
            return null;
        }
        StringBuilder sb=new StringBuilder();
        tree2strChild(root,sb);
        return sb.toString();
    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/344232.html

標籤：java

上一篇：Java-前后端分離-單點登錄(SSO)

下一篇：2110 JAVASE每日復習總結鏈接匯總

【資料結構 Java 版】二叉樹的實作（超多圖、超詳解）

文章目錄

1. 樹型結構

1.1 概念

1.2 要掌握的知識點

1.3 樹的存盤形式

1.4 樹的應用

2. 二叉樹

2.1 概念

2.2 二叉樹的基本形態

2.3 兩種特殊的二叉樹

2.3.1 滿二叉樹

2.3.2 完全二叉樹

2.4 二叉樹的性質

2.5 二叉樹的存盤

2.6 二叉樹的基本操作

2.6.1 二叉樹的前、中、后序遍歷（遞回實作）

2.6.2 二叉樹的層序遍歷

2.6.2 二叉樹的實作

2.7 前中后序的非遞回實作

3. 二叉樹練習題

3.1 二叉樹基礎練習題

3.1.1 二叉樹的前序遍歷

3.1.2 二叉樹的中序遍歷

3.1.3 二叉樹的后序遍歷

3.1.4 相同的樹

3.1.5 另一棵樹的子樹

3.1.6 二叉樹的最大深度

3.1.7 平衡二叉樹

3.1.8 對稱二叉樹

3.2 二叉樹進階練習題

3.2.1 二叉樹的構建及遍歷

3.2.2 二叉樹的層序遍歷

3.2.3 二叉樹的最近公共祖先

3.2.4 二叉搜索樹與雙向鏈表

3.2.5 從前序與中序遍歷序列構造二叉樹

3.2.6 從中序與后序遍歷序列構造二叉樹

3.2.7 根據二叉樹創建字串