---

直接刷題鏈接直達

• 非遞歸實現求二叉樹的深度
  • 引入隊列，統計當前層次節點數目，逐層遍歷
  • 二叉樹的深度（遞歸和非遞歸）
  • 102. 二叉樹的層次遍歷
• 非遞歸從左至右打印一顆二叉樹中的所有路徑
  • 257. 二叉樹的所有路徑
• 判斷平衡二叉樹
  • 110. 平衡二叉樹
• 尋找二叉搜索樹中第一個大于k的節點
  • 中序遍歷求值
  • 類似于 230. 二叉搜索樹中第K小的元素
• 二叉樹的完全性檢驗
  • 958. 二叉樹的完全性檢驗
• 根據前&中序遍歷結果重建二叉樹
  • 首先找到根節點，再劃分左右子樹區域，逐層遞歸找到左右子節點
  • 105. 從前序與中序遍歷序列構造二叉樹
• 實現一個二叉搜索樹迭代器，包括 next() 和 hasNext() 方法（PayPal）
  • 173. 二叉搜索樹迭代器
• 二叉樹的右視圖（Shopee）
  • 199. 二叉樹的右視圖
• 給定一個二叉樹根節點和指定路徑，判斷二叉樹中是否存在給定指定路徑，且要求指定路徑最后一個元素為葉節點
• 將一顆二叉搜索樹轉化成一個排序的雙向鏈表
  • 不能創建新結點
  • 二叉搜索樹與雙向鏈表
• 二叉樹的最近公共祖先
  • 首先判斷當前節點是否為指定結點，是則返回
  • 遞歸當前結點的左右子樹
  • 如果兩邊均不為null，表示找到，返回當前結點，均為null則返回null，否則返回對應子節點（left / right）
  • 236. 二叉樹的最近公共祖先
  • Lowest Common Ancestor Binary Tree（各種情況詳細舉例，推薦）
• 二叉樹的中序遍歷的下一個結點
  • 先判斷右子結點不為空，返回右子節點最左邊的節點
  • 若父節點不為空，上溯到根節點的 “/”即返回
  • 二叉樹的下一個結點
• 紅黑樹描述及其復雜度分析（插入/查找）
  • 查找、插入、刪除時間復雜度 --> O(logN)
  • 紅黑樹 Wiki
  • 26 | 紅黑樹（下）：掌握這些技巧，你也可以實現一個紅黑樹 （紅黑樹分析）
• 二叉樹的直徑
  • 543. 二叉樹的直徑
• 二叉樹的遍歷
  • 二叉樹的前序遍歷 / 二叉樹的中序遍歷 / 二叉樹的后序遍歷

---

非遞歸實現求二叉樹的深度

題目： 給定一個二叉樹 root ，返回其最大深度。
二叉樹的 最大深度 是指從根節點到最遠葉子節點的最長路徑上的節點數。

遞歸：

class Solution {public int maxDepth(TreeNode root) {if (root == null) return 0;int left = maxDepth(root.left);int right = maxDepth(root.right);return (left > right ? left:right) +1;}
}

非遞歸：
引入隊列，統計當前層次節點數目，逐層遍歷

class Solution {public int maxDepth(TreeNode root) {if (root == null) return 0;Queue<TreeNode> q = new LinkedList<>();q.offer(root);int depth = 0;while (!q.isEmpty()) {depth++;int total = q.size(); // 統計這層的數量=》全部出隊列，然后他們的子節點入隊while (total-- > 0) {TreeNode temp = q.poll();if (temp.left != null) {q.offer(temp.left);}if (temp.right != null) {q.offer(temp.right);}}}return depth;}
}

---

非遞歸從左至右打印一顆二叉樹中的所有路徑

題目： 給你一個二叉樹的根節點 root ，按 任意順序 ，返回所有從根節點到葉子節點的路徑。

遞歸：

class Solution {public List<String> binaryTreePaths(TreeNode root) {treePath(root, "");return res;}List<String> res = new ArrayList<>();public void treePath(TreeNode root, String path) {if (root == null) {return;}// 葉子節點if (root.left == null && root.right == null) {res.add(path+root.val);return;}treePath(root.left, path+root.val+"->");treePath(root.right, path+root.val+"->");}
}

非遞歸：

class Solution {// 257. 二叉樹的所有路徑public List<String> binaryTreePaths(TreeNode root) {List<String> res = new LinkedList<>();if (root == null) return res;// 存放 節點Stack<TreeNode> nodeStack = new Stack<>();// 存放 pathStack<String> pathStack = new Stack<>();// 根節點 入棧nodeStack.push(root);pathStack.push(root.val + "");while (!nodeStack.isEmpty()) {TreeNode node = nodeStack.pop();String path = pathStack.pop();if (node.left == null && node.right == null) {res.add(path);}if (node.right != null) {pathStack.push(path + "->" + node.right.val);nodeStack.push(node.right);}if (node.left != null) {pathStack.push(path + "->" + node.left.val);nodeStack.push(node.left);}}return res;}
}

---

判斷平衡二叉樹

題目：給定一個二叉樹，判斷它是否是 平衡二叉樹

class Solution {public boolean isBalanced(TreeNode root) {if (root == null) return true;if(Math.abs(findDepth(root.left)-findDepth(root.right)) > 1) return false;return isBalanced(root.left) && isBalanced(root.right);}public int findDepth(TreeNode root) {if (root == null) return 0;int left = findDepth(root.left);int right = findDepth(root.right);return (left > right ? left:right)+1;}
}

---

二叉搜索樹中第K小的元素

題目： 給定一個二叉搜索樹的根節點 root ，和一個整數 k ，請你設計一個算法查找其中第 k 小的元素（從 1 開始計數）。

class Solution {List<Integer> list;public int kthSmallest(TreeNode root, int k) {list = new ArrayList<>();inOrder(root);return list.get(k-1);}public void inOrder(TreeNode root) {if (root == null) return;inOrder(root.left);list.add(root.val);inOrder(root.right);}}

---

二叉樹的完全性檢驗

題目： 給你一棵二叉樹的根節點 root ，請你判斷這棵樹是否是一棵 完全二叉樹 。

對于一個完全二叉樹，層序遍歷的過程中遇到第一個空節點之后不應該再出現非空節點

class Solution {public boolean isCompleteTree(TreeNode root) {if (root == null) return true;// 層次遍歷Queue<TreeNode> q = new LinkedList<>();q.offer(root);boolean flag = false; // 開始出現 null 節點while(!q.isEmpty()) {TreeNode t = q.poll();if (flag && t != null) {return false;}if (t == null) {flag = true;}else {q.offer(t.left);q.offer(t.right);}}return true;}
}

---

根據前&中序遍歷結果重建二叉樹

題目：給定兩個整數數組 preorder 和 inorder ，其中 preorder 是二叉樹的先序遍歷， inorder 是同一棵樹的中序遍歷，請構造二叉樹并返回其根節點。

class Solution {private HashMap<Integer, Integer> inorderMap; // 存放中序值和索引private int preorderIndex = 0;// 當前訪問的前序的位置public TreeNode buildTree(int[] preorder, int[] inorder) {inorderMap = new HashMap<>();for (int i = 0; i < inorder.length; i++) {inorderMap.put(inorder[i], i);}return createTree(preorder, 0, inorder.length-1);}public TreeNode createTree(int[] preorder, int left, int right) {if (left > right) return null;int val = preorder[preorderIndex++];TreeNode root = new TreeNode(val);root.left = createTree(preorder, left, inorderMap.get(val)-1);root.right = createTree(preorder, inorderMap.get(val)+1, right);return root;}
}

---

二叉樹的最近公共祖先

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

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

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

---

二叉樹的直徑

給你一棵二叉樹的根節點，返回該樹的 直徑 。

二叉樹的 直徑 是指樹中任意兩個節點之間最長路徑的 長度 。這條路徑可能經過也可能不經過根節點 root 。

兩節點之間路徑的 長度 由它們之間邊數表示。

class Solution {// 543 二叉樹的直徑private int maxDiameter = 0;public int diameterOfBinaryTree(TreeNode root) {maxDepth(root); // 在計算深度的過程中更新最大直徑return maxDiameter;}// 計算樹的最大深度，同時更新最大直徑private int maxDepth(TreeNode node) {if (node == null) {return 0;}int left = maxDepth(node.left); // 左子樹深度int right = maxDepth(node.right); // 右子樹深度// 更新直徑：左子樹深度 + 右子樹深度maxDiameter = Math.max(maxDiameter, left + right);// 返回當前節點的深度return Math.max(left, right) + 1;}}

---

二叉樹的遍歷

前序遍歷：

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

中序遍歷：

class Solution {// 92 中序遍歷public List<Integer> inorderTraversal(TreeNode root) {inorder(root);return ans;}List<Integer> ans = new ArrayList<>();public void inorder(TreeNode root) {if (root == null) return;inorder(root.left);ans.add(root.val);inorder(root.right);}
}

后續遍歷：

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

---