理論基礎

二叉樹在結構上的兩個常用類型：

• 滿二叉樹
• 完全二叉樹

在功能應用上的比較常用的有：

• 二叉搜索樹： 節點有權值、遵循”左小右大“
• 平衡二叉搜索樹（AVL樹）： 在二叉樹的基礎上增添了一個特性，左右子樹高度差不超過1

二叉樹的存儲方式：

• 順序存儲：使用數組，在內存中連續分布

• 鏈式存儲：使用指針，在內存中離散分布

二叉樹的遍歷方式：

• 深度優先遍歷（可借助棧）
  • 前序遍歷（遞歸法，迭代法）
  • 中序遍歷（遞歸法，迭代法）
  • 后序遍歷（遞歸法，迭代法）
• 廣度優先遍歷（可借助隊列）
  • 層序遍歷（迭代法）

二叉樹的定義

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

二叉樹的遞歸遍歷

前序遍歷

題目鏈接：144. 二叉樹的前序遍歷

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();preRead(root,result);return result;}public void preRead(TreeNode node,List<Integer> list){if(node == null) return;list.add(node.val);preRead(node.left,list);preRead(node.right,list);}
}

中序遍歷

題目鏈接：94. 二叉樹的中序遍歷

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

后序遍歷

題目鏈接：145. 二叉樹的后序遍歷

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();postRead(root,result);return result;}public void postRead(TreeNode node,List<Integer> list){if(node == null) return;postRead(node.left,list);postRead(node.right,list);list.add(node.val);}
}

總結

遞歸算法的三要素：

• 確定遞歸函數的參數和返回值： 確定哪些參數是遞歸的過程中需要處理的，那么就在遞歸函數里加上這個參數， 并且還要明確每次遞歸的返回值是什么進而確定遞歸函數的返回類型。

  • 通過”參數傳遞“自頂向下傳遞信息
  • 通過”函數返回值“自底向上傳遞信息
  • 使用全局變量，在各級函數間共享信息

• 確定終止條件： 寫完了遞歸算法, 運行的時候，經常會遇到棧溢出的錯誤，就是沒寫終止條件或者終止條件寫的不對，操作系統也是用一個棧的結構來保存每一層遞歸的信息，如果遞歸沒有終止，操作系統的內存棧必然就會溢出。

• 確定單層遞歸的邏輯： 確定每一層遞歸需要處理的信息。在這里也就會重復調用自己來實現遞歸的過程。

二叉樹的層序遍歷

基礎層序遍歷

題目鏈接：102. 二叉樹的層序遍歷

層序遍歷的邏輯：

• 初始化一個隊列
• 首先將根節點放入隊列中
• 接下來循環往復如下操作
  • 彈出隊頭元素
  • 將彈出元素的左右節點入隊

這個題的要求在層序遍歷的基礎上增加了分層的邏輯，解題邏輯如下：

• 在層序遍歷的基礎上
• 我們再初始化一個隊列temp（主隊列命名為queue）
• 我們在queue中把當前層的元素彈出時，并不立馬將其左右元素入隊queue，而是將其添加到temp隊列中
• 當queue中所有元素彈完之后，再將temp的元素全部添加到queue中
• 這樣就達成了queue中永遠是二叉樹中每層的所有元素

解題邏輯：

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();Deque<TreeNode> queue = new ArrayDeque<>();if(root == null) return new ArrayList<List<Integer>>();queue.add(root);while(!queue.isEmpty()) {List<Integer> part = new ArrayList<>();Deque<TreeNode> temp = new ArrayDeque<>();while (!queue.isEmpty()) {TreeNode node = queue.poll();part.add(node.val);if(node.left != null) temp.add(node.left);if(node.right != null) temp.add(node.right);}result.add(part);while(!temp.isEmpty()) queue.add(temp.poll());}return result;}
}

這個地方可以進一步改進：

• 無需使用新的隊列來臨時存儲一層的元素
• 而是可以直接用一個變量界定一層的元素個數

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new LinkedList<>();Deque<TreeNode> queue = new ArrayDeque<>();if(root == null) return new ArrayList<List<Integer>>();queue.add(root);while(!queue.isEmpty()) {List<Integer> part = new LinkedList<>();int count = queue.size();while (count > 0) {TreeNode node = queue.poll();part.add(node.val);if(node.left != null) queue.add(node.left);if(node.right != null) queue.add(node.right);count--;}result.add(part);}return result;}
}

二叉樹的右視圖

題目鏈接：199. 二叉樹的右視圖

解題邏輯：

• 在前一題的基礎上只將每一層的最后一個元素添加到結果集中就可以
• 我們通過控制每層的長度變量，當變量為1的時候才添加到結果集中

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