二哈：汪汪汪汪汪汪->首先祝所有的程式猿節日快樂，為你們獻上二叉樹相關的知識

二叉樹

樹型

什么是樹

樹是一種非線性的資料結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合，n等于0時為空樹，將其叫為樹是因為他看起來像一顆倒掛的樹，意思就是它的根朝上，其葉子朝下，因此也具備以下特點：
1. 有一個特殊的節點，稱為根節點，根節點沒有前驅節點，
2. 除根節點外，其余節點被分成M(M > 0)個互不相交的集合T1、T2、…、Tm，其中每一個集合 Ti (1 <= i <= m) 又是一棵與樹類似的子樹，每棵子樹的根節點有且只有一個前驅，可以有0個或多個后繼
3. 樹是遞回定義的，

樹的概念

1. 節點的度：一個節點含有的子樹的個數稱為該節點的度； 如上圖：A的為2，
2. 樹的度：一棵樹中，最大的節點的度稱為樹的度； 如上圖：樹的度為2，
葉子節點或終端節點：度為0的節點稱為葉節點； 如上圖：D E F G節點為葉節點，
3. 雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點； 如上圖：A是B的父節點，B是D和E的節點，
4. 孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點； 如上圖：B是A的孩子節點，F和G是C的孩子結點，
5. 根結點：一顆樹中沒有雙親結點的結點就叫為根結點，如圖：A，
節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；
6. 樹的高度或深度：樹中節點的最大層次； 如上圖：樹的高度為3，
注意：上面指出的概念是最基礎的同時也是最重要的，我們必須將其記住，而以下的概念只需要了解即可：
非終端節點或分支節點：度不為0的節點，
兄弟節點：具有相同父節點的節點互稱為兄弟節點，
堂兄弟節點：雙親在同一層的節點互為堂兄弟，
節點的祖先：從根到該節點所經分支上的所有節點，
子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫，
森林：由m（m>=0）棵互不相交的樹的集合稱為森林

樹型的表達

一般來說，樹的結構型別比線性結構復雜許多，其存盤難度也更加的復雜，實際中樹的存盤有許多種如：雙親表示法，孩子表示法等，我這里就講最常用的孩子兄弟表示法

class TreeNode{
int val;
TreeNode firstChild;
TreeNode nextBrother;
}

二叉樹的定義

什么是二叉樹

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

1. 每個結點最多有兩棵子樹，即二叉樹不存在度大于 2 的結點，
2. 二叉樹的子樹有左右之分，其子樹的次序不能顛倒，因此二叉樹是有序樹，

兩種特殊的二叉樹

1. 滿二叉樹: 一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹，也就是說，如果一個二叉樹的層數為K，且結點總數是 ，則它就是滿二叉樹，
2. 完全二叉樹: 完全二叉樹是效率很高的資料結構，完全二叉樹是由滿二叉樹而引出來的，對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹， 要注意的是滿二叉樹是一種特殊的完全二叉樹，

二叉樹性質

1. 若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有 (i>0)個結點，
2. 若規定只有根節點的二叉樹的深度為1，則深度為K的二叉樹的最大結點數是 (k>=0)，
3. 對任何一棵二叉樹, 如果其葉結點個數為 n0, 度為2的非葉結點個數為 n2,則有n0＝n2+1，
4. 具有n個結點的完全二叉樹的深度k為上取整，
5. 對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的順序對所有節點從0開始編號，則對于序號為i的結點有：
若i>0，雙親序號：(i-1)/2；i=0，i為根節點編號，無雙親節點
若2i+1<n，左孩子序號：2i+1，否則無左孩子
若2i+2<n，右孩子序號：2i+2，否則無右孩子

二叉樹的存盤

二叉樹的存盤結構分為：順序存盤和類似于鏈表的鏈式存盤，
其中我們只要側重于二叉樹的鏈式存盤：二叉樹的鏈式存盤是通過一個一個的節點參考起來的，常見的表示方式有二叉和三叉表示方式，具體如下：

// 孩子表示法
class TreeNode {
 int val; // 資料域
 TreeNode left; // 左孩子的參考，常常代表左孩子為根的整棵左子樹
 TreeNode right; // 右孩子的參考，常常代表右孩子為根的整棵右子樹
}
// 孩子雙親表示法
class TreeNode {
 int val; // 資料域
 TreeNode left; // 左孩子的參考，常常代表左孩子為根的整棵左子樹
 TreeNode right; // 右孩子的參考，常常代表右孩子為根的整棵右子樹
 TreeNode parent; // 當前節點的根節點
}

一般來說：我們使用最為普遍的還是孩子表示法

二叉樹的遍歷實作

所謂遍歷(Traversal)是指沿著某條搜索路線，依次對樹中每個結點均做一次且僅做一次訪問，訪問結點所做的操作依賴于具體的應用問題(比如：列印節點內容、節點內容加1)， 遍歷是二叉樹上最重要的操作之一，是二叉樹上進
行其它運算之基礎，
**在遍歷二叉樹時，如果沒有進行某種約定，每個人都按照自己的方式遍歷，得出的結果就比較混亂，如果按照某種
規則進行約定，則每個人對于同一棵樹的遍歷結果肯定是相同的，如果N代表根節點，L代表根節點的左子樹，R代
表根節點的右子樹，則根據遍歷根節點的先后次序有以下遍歷方式：

1. NLR：前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結點—>根的左子樹—>根的右子樹，
2. LNR：中序遍歷(Inorder Traversal)——根的左子樹—>根節點—>根的右子樹，
3. LRN：后序遍歷(Postorder Traversal)——根的左子樹—>根的右子樹—>根節點，**

前序遍歷

前序遍歷就是先訪問根結點再訪問根的左孩子最后再訪問根的右孩子
如圖：

遞回實作

核心代碼如下：

class TreeNode {
    int val; // 資料域
    TreeNode left; // 左孩子的參考，常常代表左孩子為根的整棵左子樹
    TreeNode right; // 右孩子的參考，常常代表右孩子為根的整棵右子樹
    public TreeNode(int val){
        this.val=val;
    }
}
public class Main {
    //先序遍歷
    public void preOrderTraversal(TreeNode root){
        //如果該根結點為空則回傳；
        if (root==null){
            return;
        }
        System.out.println(root.val);//訪問根結點
        preOrderTraversal(root.left);//開始遞回該根的左孩子
        preOrderTraversal(root.right);//開始遞回該根的右孩子
    }
}

如例題：二叉樹的前序遍歷

主要思路：該題主要考查我們對二叉樹前序遍歷的熟悉程度不過我們得注意其回傳型別為List，所以如果我們使用遞回時則需要接收他們的回傳型別
代碼如下：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret=new LinkedList<>();
          if (root==null){
              return ret;
          }
          ret.add(root.val);
          List<Integer> left=new LinkedList<>(preorderTraversal(root.left));
          ret.addAll(left);
          List<Integer> right=new LinkedList<>(preorderTraversal(root.right));
          ret.addAll(right);
          return ret;
    }
}

非遞回實作

當我們不使用遞回進行遍歷時，我們則需要借助一個堆疊用于實作二叉樹的先序遍歷，操作如下先將根結點放入堆疊中取出堆疊中的結點遍歷完成后再依次將根的右孩子左孩子放入堆疊中，進行回圈遍歷
核心代碼如下

public void preOrderTraversal(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();//創建一個堆疊
        if (root==null){
            return;
        }
        TreeNode cur=root;
        stack.push(cur);
        while (!stack.isEmpty()){
            TreeNode node=stack.pop();
            System.out.println(node.val);
            //先放右孩子，再放左孩子，因為堆疊是先進先出的特點
            if(node.right!=null){
                //右孩子不為空則將其放入堆疊里面
                stack.push(node.right);
            }
            if (node.left!=null){
                //左孩子不為空則將其放入堆疊里面
                stack.push(node.left);
            }
        }
    }

中序遍歷

中序遍歷就是先訪問根的左孩子再訪問根，最后再訪問根的右孩子
如圖：

遞回實作

核心代碼如下：

class TreeNode {
    int val; // 資料域
    TreeNode left; // 左孩子的參考，常常代表左孩子為根的整棵左子樹
    TreeNode right; // 右孩子的參考，常常代表右孩子為根的整棵右子樹
    public TreeNode(int val){
        this.val=val;
    }
}
//中序遍歷
    public void inOrderTraversal(TreeNode root){
        //如果該根結點為空則回傳；
        if (root==null){
            return;
        }
        inOrderTraversal(root.left);//開始遞回該根的左孩子
        System.out.println(root.val);//訪問結點
        inOrderTraversal(root.right);//開始遞回該根的右孩子
    }

二叉樹的中序遍歷

思路：其考查二叉樹的中序遍歷，其細節與之上的一樣

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
         List<Integer> ret=new LinkedList<>();
        if (root==null){
            return ret;
        }
       // 
        List<Integer> left=inorderTraversal(root.left);
        ret.addAll(left);
        ret.add(root.val);
        List<Integer> right=inorderTraversal(root.right);
        ret.addAll(right);
        return ret;
    }
}

非遞回實作

當我們不使用遞回進行遍歷時，我們則需要借助一個堆疊用于實作二叉樹的先序遍歷，操作如下先將根的孩子放入，堆疊中取出堆疊頂的結點，遍歷完成后再依次將根的右孩子左孩子放入堆疊中，進行回圈遍歷
核心代碼如下

public void inOrderTraversal(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        if (root==null){//判斷樹是否為空
            return;
        }
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){//將左孩子放入其中
                stack.push(cur);
                cur=cur.left;
            }
            cur=stack.pop();
            System.out.println(cur.val);
            cur=cur.right;
        }
    }

后序遍歷

后序遍歷就是先訪問根的左孩子，右孩子最后訪問根結點
如圖：

遞回遍歷

class TreeNode {
    int val; // 資料域
    TreeNode left; // 左孩子的參考，常常代表左孩子為根的整棵左子樹
    TreeNode right; // 右孩子的參考，常常代表右孩子為根的整棵右子樹
    public TreeNode(int val){
        this.val=val;
    }
}
//后序遍歷
    public void postOrderTraversal(TreeNode root){
        //如果該根結點為空則回傳；
        if (root==null){
            return;
        }
        postOrderTraversal(root.left);//開始遞回該根的左孩子
        postOrderTraversal(root.right);//開始遞回該根的右孩子
        System.out.println(root.val);//訪問結點
    }

二叉樹的后序遍歷

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret=new LinkedList<>();
        if (root==null){
            return ret;
        }
        List<Integer> left=postorderTraversal(root.left);
        ret.addAll(left);
        List<Integer> right=postorderTraversal(root.right);
        ret.addAll(right);
        ret.add(root.val);
        return ret;
    }
}

非遞回遍歷

與先序中序非遞回遍歷一樣，都需要使用一個堆疊，方法也一樣不過在遍歷的時候需要進行一次判斷判斷該需要遍歷的結點右孩子為慷訓者或者其右孩子已經被遍歷如果滿足以上的條件則進行遍歷，

public void postOrderTraversal(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        if (root==null){
            return;
        }
        TreeNode prev=null;
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            cur=stack.peek();
            //如果該結點的右孩子為慷訓者或者其右孩子已經被遍歷
            if (cur.right==null||cur.right==prev){
                System.out.println(cur.val);
                stack.pop();
                prev=cur;
                cur = null;// 這個cur被列印了不能再次入堆疊
            }
            else {
                cur=cur.right;
            }
        }
    }

二叉樹的層次遍歷

設二叉樹的根節點所在層數為1，層序遍歷就是從所在二叉樹的根節點出發，首先訪問第一層的樹根節點，然后從左到右訪問第2層上的節點，接著是第三層的節點，以此類推，自上而下，自左至右逐層訪問樹的結點的程序就是
層序遍歷，
如圖：

public void levelOrderTraversal(TreeNode root) {
        if(root == null) return;//判斷該樹是否為空
        Queue<TreeNode> queue = new LinkedList<>();//創建一個佇列
        queue.offer(root);//放入根結點
        while (!queue.isEmpty()) {
            TreeNode top = queue.poll();
            System.out.print(top.val+" ");
            if(top.left != null) {//判斷左孩子是否為空
                queue.offer(top.left);
            }
            if(top.right!=null) {//判斷右孩子是否為空
                queue.offer(top.right);
            }
        }
    }