二叉樹理論基礎

二叉樹種類

滿二叉樹：每個非葉子節點都有且只有兩個子節點。

和完全二叉樹：除了最底層外，其他各層都是滿的；最底層的節點都集中在左側。

二叉搜索樹：對于任意節點 u，左子樹上所有節

點的值都小于 u.val，右子樹上所有節點的值都大于 u.val。

平衡二叉樹：任意節點的左右子樹高度差 ≤ 1。

二叉樹的存儲方式

「二叉樹可以鏈式存儲，也可以順序存儲。」

那么鏈式存儲方式就用指針，順序存儲的方式就是用數組。

遍歷算法

深度優先遍歷（DFS）

前序（Pre?Order）：根 → 左 → 右

/*** 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> res = new LinkedList<>();preorder(root, res);return res;}void preorder(TreeNode root,List<Integer> list){if(root == null){return;}list.add(root.val);preorder(root.left,list);        preorder(root.right,list);}
}

中序（In?Order）：左 → 根 → 右


class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new LinkedList<>();inorder(root, res);return res;}void inorder(TreeNode root,List<Integer> list){if(root == null){return;}inorder(root.left,list);list.add(root.val);inorder(root.right,list);}
}

后序（Post?Order）：左 → 右 → 根


class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new LinkedList<>();inorder(root, res);return res;}void inorder(TreeNode root,List<Integer> list){if(root == null){return;}           inorder(root.left,list);        inorder(root.right,list);list.add(root.val);}
}

廣度優先遍歷（BFS）/層序（Level?Order）
- 按層自上而下、同層從左到右依次訪問，通常用隊列實現。

?二叉樹的定義

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

遞歸寫法?

確定遞歸函數的參數和返回值：?確定哪些參數是遞歸的過程中需要處理的，那么就在遞歸函數里加上這個參數，并且還要明確每次遞歸的返回值是什么進而確定遞歸函數的返回類型。
確定終止條件：?寫完了遞歸算法, 運行的時候，經常會遇到棧溢出的錯誤，就是沒寫終止條件或者終止條件寫的不對，操作系統也是用一個棧的結構來保存每一層遞歸的信息，如果遞歸沒有終止，操作系統的內存棧必然就會溢出。
確定單層遞歸的邏輯：?確定每一層遞歸需要處理的信息。在這里也就會重復調用自己來實現遞歸的過程。

以前序遍歷為例：

1.首先，確認參數，因為我們訪問的是節點，所以參數要包含節點對象，其次要返回訪問的數值，所以也要包含一個list對象保存訪問的值

2.每一層遞歸的終止條件就是遇見空節點，所以判斷當前節點是否為空，為空就返回

3.?前序遍歷是中左右的順序，所以在單層遞歸的邏輯，是要先取中節點的數值，代碼如下：

迭代解決遍歷

前序：因為迭代使用棧，而出棧順序是先進后出，所以我們在遍歷的時候要改變遍歷的順序，先遍歷右節點，在遍歷左節點，這時候就是左節點先出，符合根左右的習慣

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if(root == null){return list;}Stack<TreeNode> s = new Stack<>();s.push(root);while(!s.isEmpty()){TreeNode node = s.pop();list.add(node.val);if(node.right != null){s.push(node.right);}if(node.left != null){s.push(node.left);}}return list;
}}

中序：在使用迭代法寫中序遍歷，就需要借用指針的遍歷來幫助訪問節點，棧則用來處理節點上的元素。

// 中序遍歷順序: 左-中-右 入棧順序： 左-右
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()){if (cur != null){stack.push(cur);cur = cur.left;}else{cur = stack.pop();result.add(cur.val);cur = cur.right;}}return result;}
}

后序：// 后序遍歷順序左-右-中入棧順序：中-左-右出棧順序：中-右-左，最后翻轉結果

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()){TreeNode node = stack.pop();result.add(node.val);if (node.left != null){stack.push(node.left);}if (node.right != null){stack.push(node.right);}}Collections.reverse(result);return result;}
}

!!層次遍歷

思路：需要借助輔助隊列來完成統計，即一層一層的入隊。

1.首先聲明一個外部的輔助隊列，用來統計所有的入隊出隊的值，

2.聲明處理一層一層隊列的方法，在方法內部創建一個內部隊列用來處理每一層中出對入對的值

3.每一層結束的標記是什么，就是內部隊列長度為0時，就結束.

public class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> resList = new LinkedList<>();if (root == null) {return resList;}Queue<TreeNode> q = new LinkedList<>();q.add(root);while (!q.isEmpty()) {List<Integer> l = new ArrayList<>();int len = q.size();while (len > 0) {TreeNode node = q.poll();l.add(node.val);if (node.left != null)  q.add(node.left);if (node.right != null) q.add(node.right);len--;}resList.add(l);}return resList;
}}

二叉樹自底而上的層次遍歷

給你二叉樹的根節點?root?，返回其節點值?自底向上的層序遍歷?。（即按從葉子節點所在層到根節點所在的層，逐層從左向右遍歷）

利用LinkedList的addFirst()方法即可，每一次遍歷完都將內部隊列得到的值放在前面，即可倒序

！！注意如果將res實際實現為List類型，就無法使用addFirst()方法?

LinkedList<List<Integer>> res = new LinkedList<>();

public List<List<Integer>> levelOrder(TreeNode root) {LinkedList<List<Integer>> res = new LinkedList<>();if (root == null) {return null;}Queue<TreeNode> q = new LinkedList<>();q.add(root);while (!q.isEmpty()) {List<Integer> l = new LinkedList<>();int len = q.size();while (len-- > 0) {TreeNode node = q.poll();l.add(node.val);if (node.left != null)  q.add(node.left);if (node.right != null) q.add(node.right);}res.addFirst(l);}return res;}

二叉樹的右視圖

給定一個二叉樹的?根節點?root，想象自己站在它的右側，按照從頂部到底部的順序，返回從右側所能看到的節點值。

思路很簡單，即每層層序遍歷時都將最右邊的節點值加入到LIst中，如何判斷為最右邊的節點？

即每一層處理時，隊列長度僅為1時就是最右邊的節點

class Solution {public List<Integer> rightSideView(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}Queue<TreeNode> q = new LinkedList<>();q.add(root);while (!q.isEmpty()) {int len = q.size();while (len > 0) {TreeNode node = q.poll();if(len == 1){res.add(node.val);}if (node.left != null)  q.add(node.left);if (node.right != null) q.add(node.right);len--;}}return res;}
}

完全二叉樹的節點個數

很簡單，利用層次遍歷計算每一次處理隊列中結點的數量即可

class Solution {public int countNodes(TreeNode root) {Queue<TreeNode> q = new LinkedList<>();if(root == null){return 0;}q.add(root);int count=0;while(!q.isEmpty()){int size = q.size();for(int i=0;i<size;i++){TreeNode node = q.poll();count++;if(node.left !=null)q.add(node.left);if(node.right !=null)q.add(node.right);}}return count;}
}

二叉樹節點的深度：指從根節點到該節點的最長簡單路徑邊的條數。
二叉樹節點的高度：指從該節點到葉子節點的最長簡單路徑邊的條數。

二叉樹的最大深度

使用層次遍歷到最底一層的節點，既可以判斷深度大小

class Solution {/*** 迭代法，使用層序遍歷*/public int maxDepth(Node root) {if (root == null)   return 0;int depth = 0;Queue<Node> que = new LinkedList<>();que.offer(root);while (!que.isEmpty()){depth ++;int len = que.size();while (len > 0){Node node = que.poll();for (int i = 0; i < node.children.size(); i++)if (node.children.get(i) != null) que.offer(node.children.get(i));len--;}}return depth;}
}
遞歸用法
class Solution {public int maxDepth(TreeNode root) {//終止條件：當樹為空時結束遞歸，并返回當前深度0if(root == null){return 0;}//root的左、右子樹的最大深度int leftDepth = maxDepth(root.left);int rightDepth = maxDepth(root.right);//返回的是左右子樹的最大深度+1return Math.max(leftDepth, rightDepth) + 1;}
}

通過二叉樹的最大深度遞歸用法，我們可以總結一下里面遞歸的過程，比如有一個{1，2，3，4，5，6，7，8}的完全二叉樹

1.首先，節點1不為空，進入棧內，然后先調用左子樹，這時，節點2入棧，4入棧，8入棧，因為每次都先判斷的左子樹。

2.這時候棧內又遞歸調用的maxdepth(8),maxdepth(4),maxdepth(2),maxdepth(1)，然后節點8沒有左右子樹，所以leftdepth和rightdepth都是0，然后返回0+1，這是maxdepth(8)出棧了，回到maxdepth(4)，這時候傳遞的leftdepth=1，因為8時4的左節點，節點4沒有右節點，所以rightdepth=0，這是返回1+1，4出棧，返回maxdepth(2)，leftdepth=2，rightdepth=1,所以返回2+1，2出棧，返回maxdepth(1)，leftdepth=3，進入右子樹。。。。

3.最后又返回maxdepth(1),leftdepth=3,rightdepth=2,所以最后的值返回的時3+1

遞歸調用棧過程

節點1入棧：
- 調用左子樹?maxDepth(2)。
節點2入棧：
- 調用左子樹?maxDepth(4)。
節點4入棧：
- 調用左子樹?maxDepth(8)。
節點8入棧：
- 左子樹為空，返回?0。
- 右子樹為空，返回?0。
- 當前節點8的深度為?max(0, 0) + 1 = 1，出棧。
回到節點4：
- leftDepth = 1（來自節點8）。
- 調用右子樹?maxDepth(null)，返回?0。
- 當前節點4的深度為?max(1, 0) + 1 = 2，出棧。
回到節點2：
- leftDepth = 2（來自節點4）。
- 調用右子樹?maxDepth(5)。
節點5入棧：
- 左子樹為空，返回?0。
- 右子樹為空，返回?0。
- 當前節點5的深度為?max(0, 0) + 1 = 1，出棧。
回到節點2：
- rightDepth = 1（來自節點5）。
- 當前節點2的深度為?max(2, 1) + 1 = 3，出棧。
回到節點1：
- leftDepth = 3（來自節點2）。
- 調用右子樹?maxDepth(3)。
節點3入棧：
- 調用左子樹?maxDepth(6)。
節點6入棧：
- 左子樹為空，返回?0。
- 右子樹為空，返回?0。
- 當前節點6的深度為?max(0, 0) + 1 = 1，出棧。
回到節點3：
- leftDepth = 1（來自節點6）。
- 調用右子樹?maxDepth(7)。
節點7入棧：
- 左子樹為空，返回?0。
- 右子樹為空，返回?0。
- 當前節點7的深度為?max(0, 0) + 1 = 1，出棧。
回到節點3：
- rightDepth = 1（來自節點7）。
- 當前節點3的深度為?max(1, 1) + 1 = 2，出棧。
回到節點1：
- rightDepth = 2（來自節點3）。
- 當前節點1的深度為?max(3, 2) + 1 = 4，出棧。