LeetCode 二叉樹系統題解
- 2019 年 11 月 11 日
- 筆記
LeetCode 樹的定義
二叉樹
public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }N叉樹
public class Node { public int val; public List<Node> children; public Node() { } public Node(int _val, List<Node> _children) { val = _val; children = _children; } }二叉樹遍歷
二叉樹最基本的遍歷方式就是：前序遍歷、中序遍歷和後序遍歷。
- 前序遍歷首先訪問根節點，然後遍歷左子樹，最後遍歷右子樹。
- 中序遍歷是先遍歷左子樹，然後訪問根節點，然後遍歷右子樹。
- 後序遍歷是先遍歷左子樹，然後遍歷右子樹，最後訪問樹的根節點。
簡單概況如下：
- 前序遍歷：根左右
- 中序遍歷：左根右
- 後序遍歷：左右根
TIPS：前中後序遍歷區別在於三字中的中間那個字，前、中、後序分別對應左、根、右。
二叉樹前序遍歷
- 二叉樹的前序遍歷
給定一個二叉樹，返回它的 前序 遍歷。
示例:
輸入: [1,null,2,3] 1 2 / 3 輸出: [1,2,3]
進階: 遞歸演算法很簡單，你可以通過迭代演算法完成嗎？
遞歸
public List<Integer> preorderTraversal(TreeNode root) { List<Integer> ans = new ArrayList<>(); robot(root, ans); return ans; } private void robot(TreeNode p, List<Integer> ans) { if(p == null) return; // 根左右 ans.add(p.val); robot(p.left, ans); robot(p.right, ans); }迭代
迭代步驟：
- 從根節點開始，每次迭代彈出當前棧頂元素
- 將其孩子節點壓入棧中（先壓右孩子再壓左孩子）
public List<Integer> preorderTraversal2(TreeNode root) { List<Integer> ans = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); // 將根節點入棧 stack.push(root); while (!stack.isEmpty()) { // 取出棧頂元素 TreeNode tmp = stack.pop(); if (tmp != null) { ans.add(tmp.val); // 將其孩子節點壓入棧中（先右節點、再左節點） stack.add(tmp.right); stack.add(tmp.left); } } return ans; }演算法複雜度:
- 時間複雜度：樹中每個節點都遍歷一次，因此時間複雜度為 O(N)，其中 N 為樹中節點的數量。
- 空間複雜度：
- 最壞情況：樹為鏈表，樹的高度=樹的節點個數，此時空間複雜度是 O(N)。
- 最好情況：樹高度平衡，此時空間複雜度是 O(logn)。
二叉樹中序遍歷
- 二叉樹的中序遍歷
給定一個二叉樹，返回它的 中序 遍歷。
示例:
輸入: [1,null,2,3] 1 2 / 3 輸出: [1,3,2]
進階: 遞歸演算法很簡單，你可以通過迭代演算法完成嗎？
遞歸
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> ans = new ArrayList<>(); robot(root, ans); return ans; } private void robot(TreeNode root, List<Integer> ans) { if (root == null) { return; } // 左根右 robot(root.left, ans); ans.add(root.val); robot(root.right, ans); }迭代
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> ans = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); while (!stack.isEmpty() || root != null) { // 一直放入左兒子（左） while (root != null) { stack.push(root); root = root.left; } // 訪問當前元素（根），把右兒子入棧（右） if (!stack.isEmpty()) { root = stack.pop(); ans.add(root.val); root = root.right; } } return ans; }演算法複雜度
- 時間複雜度：O(n)。遞歸函數 T(n) = 2⋅T(n/2)+1。
- 空間複雜度：最壞情況下需要空間O(n)，平均情況為O(logn)。
二叉樹後序遍歷
- 二叉樹的後序遍歷
給定一個二叉樹，返回它的 後序 遍歷。
示例:
輸入: [1,null,2,3] 1 2 / 3 輸出: [3,2,1]
進階: 遞歸演算法很簡單，你可以通過迭代演算法完成嗎？
遞歸
public List<Integer> postorderTraversal(TreeNode root) { List<Integer> ans = new ArrayList<>(); robot(root, ans); return ans; } private void robot(TreeNode p, List<Integer> ans) { if (p == null) { return; } // 左右根 robot(p.left, ans); robot(p.right, ans); ans.add(p.val); }後序遍歷的非遞歸寫法有些麻煩，因為節點第一次訪問時並不列印，而是在第二次遍歷時才列印。所以需要一個變數來標記該結點是否訪問過。
迭代：利用輔助類
public class StackNode { TreeNode root; boolean visit; StackNode(TreeNode root) { this.root = root; } } public List<Integer> postorderTraversal2(TreeNode root) { List<Integer> ans = new ArrayList<>(); if (root == null) { return ans; } Stack<StackNode> stack = new Stack<>(); StackNode node; stack.push(new StackNode(root)); while (!stack.isEmpty()) { node = stack.pop(); if (node == null) { continue; } if (!node.visit) { node.visit = true; stack.push(node); if (node.root.right != null) { stack.push(new StackNode(node.root.right)); } if (node.root.left != null) { stack.push(new StackNode(node.root.left)); } } else if (node.root != null) { ans.add(node.root.val); } } return ans; }迭代：逆序輸出
public List<Integer> postorderTraversal3(TreeNode root) { LinkedList<Integer> ans = new LinkedList<>(); if (root == null) { return ans; } Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); ans.addFirst(node.val); if (node.left != null) { stack.push(node.left); } if (node.right != null) { stack.push(node.right); } } return ans; }演算法複雜度：
- 時間複雜度：訪問每個節點恰好一次，因此時間複雜度為 O(N)，其中 N 是節點的個數，也就是樹的大小。
- 空間複雜度：取決於樹的結構，最壞情況需要保存整棵樹，因此空間複雜度為 O(N)。
二叉樹的層次遍歷
- 二叉樹的層次遍歷
給定一個二叉樹，返回其按層次遍歷的節點值。 （即逐層地，從左到右訪問所有節點）。
例如：給定二叉樹: [3,9,20,null,null,15,7],
3 / 9 20 / 15 7
返回其層次遍歷結果：
[ [3], [9,20], [15,7] ]
遞歸
首先確認樹非空，然後調用遞歸函數 helper(node, level)，參數是當前節點和節點的層次。
演算法過程:
- ans 為結果列表，level 為當前遍歷的層數（初始為0）
- 若 ans 的長度 = level，向 ans 增加一個空列表
- 將節點值放入 ans 的第 level 個列表結尾
- 遍歷左右子節點，此時 level + 1
public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); robot(root, ans, 0); return ans; } private void robot(TreeNode root, List<List<Integer>> ans, int level) { if (root == null) { return; } if (ans.size() == level) { ans.add(new ArrayList()); } ans.get(level).add(root.val); robot(root.left, ans, level + 1); robot(root.right, ans, level + 1); }複雜度分析
- 時間複雜度：O(N)，因為每個節點恰好會被運算一次。
- 空間複雜度：O(N)，保存輸出結果的數組包含 N 個節點的值。
迭代
演算法過程：
第 0 層只包含根節點 root ，演算法實現如下：
- 初始化隊列只包含一個節點 root 和層次編號 0 ： level = 0。
- 當隊列非空的時候：
- 新建一個空列表，表示當前層結果 current。
- 計算當前層有多少個元素：等於隊列的長度。
- 將這些元素從隊列中彈出，並加入 current 列表中。
- 將他們的孩子節點作為下一層壓入隊列中。
- 將 當前層結果 current 放入 ans 中。
- 進入下一層循環。
public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); if (root == null) { return ans; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { List<Integer> current = new ArrayList<>(); // 當前層的元素個數 int length = queue.size(); for (int i = 0; i < length; ++i) { TreeNode node = queue.remove(); // 放入結果 current.add(node.val); // 依次將 node 的左右子節點加入隊列 if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } ans.add(current); } return ans; }複雜度分析
- 時間複雜度：O(N)，因為每個節點恰好會被運算一次。
- 空間複雜度：O(N)，保存輸出結果的數組包含 N 個節點的值。
二叉樹的右視圖
- 二叉樹的右視圖
給定一棵二叉樹，想像自己站在它的右側，按照從頂部到底部的順序，返回從右側所能看到的節點值。
示例:
輸入: [1,2,3,null,5,null,4] 輸出: [1, 3, 4] 解釋: 1 <--- / 2 3 <--- 5 4 <---
本題是層序遍歷的變種，層序遍歷是存儲二叉樹每行的每個元素，而本題僅存儲二叉樹每行的最後一個元素。
遞歸
public List<Integer> rightSideView(TreeNode root) { List<Integer> ans = new ArrayList<>(); robot(root, ans, 0); return ans; } private void robot(TreeNode root, List<Integer> ans, int level) { if (root == null) { return; } if (ans.size() == level) { ans.add(root.val); } // 層序遍歷的 ans 是一個 List<List<Integer>，是 ans.get(level).add(root.val); ans.set(level, root.val); robot(root.left, ans, level + 1); robot(root.right, ans, level + 1); }迭代
public List<Integer> rightSideView(TreeNode root) { List<Integer> ans = new ArrayList<>(); if (root == null) { return ans; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int current = 0; // 當前層的元素個數 int length = queue.size(); for (int i = 0; i < length; ++i) { TreeNode node = queue.remove(); // 放入結果 current = node.val; // 依次將 node 的左右子節點加入隊列 if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } ans.add(current); } return ans; }在每個樹行中找最大值
- 在每個樹行中找最大值
您需要在二叉樹的每一行中找到最大的值。
示例：
輸入:
1 / 3 2 / 5 3 9 輸出: [1, 3, 9]
本題也是層序遍歷的變種，層序遍歷是存儲二叉樹每行的每個元素，而本題僅存儲二叉樹每行的最大元素。
遞歸
public List<Integer> largestValues(TreeNode root) { List<Integer> ans = new ArrayList<>(); robot(root, ans, 0); return ans; } private void robot(TreeNode root, List<Integer> ans, int level) { if (root == null) { return; } if (ans.size() <= level) { ans.add(Integer.MIN_VALUE); } ans.set(level, Math.max(ans.get(level), root.val)); robot(root.left, ans, level + 1); robot(root.right, ans, level + 1); }迭代
public List<Integer> largestValues(TreeNode root) { List<Integer> ans = new ArrayList<>(); if (root == null) { return ans; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int current = Integer.MIN_VALUE; // 當前層的元素個數 int length = queue.size(); for (int i = 0; i < length; ++i) { TreeNode node = queue.remove(); // 放入結果（變化的地方） current = Math.max(current, node.val); // 依次將 node 的左右子節點加入隊列 if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } ans.add(current); } return ans; }二叉樹的垂序遍歷
- 二叉樹的垂序遍歷
給定二叉樹，按垂序遍歷返回其結點值。
對位於 (X, Y) 的每個結點而言，其左右子結點分別位於 (X-1, Y-1) 和 (X+1, Y-1)。
把一條垂線從 X = -infinity 移動到 X = +infinity ，每當該垂線與結點接觸時，我們按從上到下的順序報告結點的值（ Y 坐標遞減）。
如果兩個結點位置相同，則首先報告的結點值較小。
按 X 坐標順序返回非空報告的列表。每個報告都有一個結點值列表。
示例 1：
image
輸入：[3,9,20,null,null,15,7] 輸出：[[9],[3,15],[20],[7]] 解釋： 在不喪失其普遍性的情況下，我們可以假設根結點位於 (0, 0)： 然後，值為 9 的結點出現在 (-1, -1)； 值為 3 和 15 的兩個結點分別出現在 (0, 0) 和 (0, -2)； 值為 20 的結點出現在 (1, -1)； 值為 7 的結點出現在 (2, -2)。
示例 2：
image
@w=400
輸入：[1,2,3,4,5,6,7] 輸出：[[4],[2],[1,5,6],[3],[7]] 解釋： 根據給定的方案，值為 5 和 6 的兩個結點出現在同一位置。 然而，在報告 "[1,5,6]" 中，結點值 5 排在前面，因為 5 小於 6。
提示：
樹的結點數介於 1 和 1000 之間。 每個結點值介於 0 和 1000 之間。
解題思路
設根節點的(x,y)=(0,0)，對於節點坐標(x,y)，其左節點坐標為(x-1,y-1)，右節點坐標為(x+1,y-1)。
- 構造 List<PositionNode> posNodes，遍歷二叉樹每個節點，填入 PositionNode 的 x 坐標、y 坐標、val 值。
- 將 posNodes 展開成 key 是 x 坐標、value 是對應 PositionNode 的 positionMap，注意這裡使用 TreeMap，因為要對 x 坐標排序。
- 構建結果 ans：遍歷 positionMap，相同位置節點，按照自然順序排序（即先按照 Y 降序排列；若 Y 相同，則按照 val 升序排列）
程式碼
public class PositionNode { int val; int x; int y; PositionNode(int val, int x, int y) { this.val = val; this.x = x; this.y = y; } public int getVal() { return val; } public int getX() { return x; } public int getY() { return y; } } public List<List<Integer>> verticalTraversal(TreeNode root) { // 構建節點的位置資訊 List<PositionNode> posNodes = new ArrayList<>(); robot(root, posNodes, 0, 0); // 將 posNodes 展開成 key 是 x 坐標、value 是對應 PositionNode 的 map // 注意這裡使用 TreeMap，因為要對 x 坐標排序 Map<Integer, List<PositionNode>> positionMap = posNodes.stream().collect( Collectors.groupingBy(PositionNode::getX, TreeMap::new, Collectors.toList())); // 構建結果 List<List<Integer>> ans = new ArrayList<>(); positionMap.forEach((k, v) -> { // 題目要求：相同位置節點，按照自然順序排序（即先按照 Y 降序排列；若 Y 相同，則按照 val 升序排列） v.sort(Comparator.comparing(PositionNode::getY).reversed() .thenComparing(PositionNode::getVal)); ans.add(v.stream().map(PositionNode::getVal).collect(Collectors.toList())); }); return ans; } private void robot(TreeNode root, List<PositionNode> posNodes, int x, int y) { if (root == null) { return; } posNodes.add(new PositionNode(root.val, x, y)); // 根節點的(x,y)=(0,0)，若某個節點坐標為(x,y)，則左節點坐標為(x-1,y-1)，右節點坐標為(x+1,y-1) robot(root.left, posNodes, x - 1, y - 1); robot(root.right, posNodes, x + 1, y - 1); }二叉樹的鋸齒形層次遍歷
- 二叉樹的鋸齒形層次遍歷
給定一個二叉樹，返回其節點值的鋸齒形層次遍歷。（即先從左往右，再從右往左進行下一層遍歷，以此類推，層與層之間交替進行）。
例如： 給定二叉樹 [3,9,20,null,null,15,7],
3 / 9 20 / 15 7
返回鋸齒形層次遍歷如下：
[ [3], [20,9], [15,7] ]
本題是層序遍歷的變種，僅需將層序遍歷的偶數行逆序即可。
遞歸
public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); robot(root, ans, 0); // 與層序遍歷相比，變化的部分 for (int i = 1; i < ans.size(); i += 2) { Collections.reverse(ans.get(i)); } return ans; } private void robot(TreeNode root, List<List<Integer>> ans, int level) { if (root == null) { return; } if (ans.size() == level) { ans.add(new ArrayList()); } ans.get(level).add(root.val); robot(root.left, ans, level + 1); robot(root.right, ans, level + 1); }迭代
public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); if (root == null) { return ans; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { List<Integer> current = new ArrayList<>(); // 當前層的元素個數 int length = queue.size(); for (int i = 0; i < length; ++i) { TreeNode node = queue.remove(); // 放入結果 current.add(node.val); // 依次將 node 的左右子節點加入隊列 if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } ans.add(current); } // 與層序遍歷相比，變化的部分 for (int i = 1; i < ans.size(); i += 2) { Collections.reverse(ans.get(i)); } return ans; }N 叉樹遍歷
N叉樹的層序遍歷
- N叉樹的層序遍歷
給定一個 N 叉樹，返回其節點值的層序遍歷。 (即從左到右，逐層遍歷)。
例如，給定一個 3叉樹 :
image
@w=400
返回其層序遍歷:
[ [1], [3,2,4], [5,6] ]
說明:
- 樹的深度不會超過 1000。
- 樹的節點總數不會超過 5000。
public List<List<Integer>> levelOrder(Node root) { List<List<Integer>> ans = new ArrayList<>(); robot(root, ans, 0); return ans; } private void robot(Node root, List<List<Integer>> ans, int level) { if (root == null) { return; } if (ans.size() <= level) { ans.add(new ArrayList<>()); } ans.get(level).add(root.val); if (root.children == null) { return; } for (Node child : root.children) { robot(child, ans, level + 1); } }N叉樹的前序遍歷
- N叉樹的前序遍歷
給定一個 N 叉樹，返回其節點值的前序遍歷。
例如，給定一個 3叉樹 :
image
@w=400
返回其前序遍歷: [1,3,5,6,2,4]。
說明: 遞歸法很簡單，你可以使用迭代法完成此題嗎？
遞歸
public List<Integer> preorder(Node root) { List<Integer> ans = new ArrayList<>(); robot(root, ans); return ans; } private void robot(Node root, List<Integer> ans) { if (root == null) { return; } ans.add(root.val); if (root.children == null) { return; } for (Node child : root.children) { robot(child, ans); } }迭代
public List<Integer> preorder(Node root) { List<Integer> ans = new ArrayList<>(); if (root == null) { return ans; } Deque<Node> deque = new ArrayDeque<>(); deque.push(root); while (!deque.isEmpty()) { Node tmp = deque.pop(); if (tmp != null) { ans.add(tmp.val); if (tmp.children == null) { continue; } for (int i = tmp.children.size() - 1; i >= 0; i--) { deque.push(tmp.children.get(i)); } } } return ans; }N叉樹的後序遍歷
- N叉樹的後序遍歷
給定一個 N 叉樹，返回其節點值的後序遍歷。
例如，給定一個 3叉樹 :
image
@w=400
返回其後序遍歷: [5,6,3,2,4,1].
說明: 遞歸法很簡單，你可以使用迭代法完成此題嗎?
遞歸
public List<Integer> postorder(Node root) { List<Integer> ans = new ArrayList<>(); robot(root, ans); return ans; } private void robot(Node root, List<Integer> ans) { if (root == null) { return; } if (root.children != null) { for (Node child : root.children) { robot(child, ans); } } ans.add(root.val); }迭代
// 後續遍歷：左右中 // 迭代順序：中右左 public List<Integer> postorder(Node root) { List<Integer> ans = new ArrayList<>(); if (root == null) { return ans; } Stack<Node> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { Node pop = stack.pop(); ans.add(pop.val); List<Node> children = pop.children; if (children == null) { continue; } for (Node child : children) { stack.push(child); } } Collections.reverse(ans); return ans; }二叉搜索樹
不同的二叉搜索樹
- 不同的二叉搜索樹
給定一個整數 n，求以 1 ... n 為節點組成的二叉搜索樹有多少種？
示例:
輸入: 3 輸出: 5 解釋: 給定 n = 3, 一共有 5 種不同結構的二叉搜索樹: 1 3 3 2 1 / / / 3 2 1 1 3 2 / / 2 1 2 3
public int numTrees(int n) { int[] ans = new int[n + 2]; ans[0] = 1; ans[1] = 1; ans[2] = 2; // f(n) = f(0)*f(n-1) + f(1)*f(n-2) + …… for(int i = 3; i <= n; i++) { for(int j = 0; j <= i - 1; j++) { ans[i] += ans[j] * ans[i - j - 1]; } } return ans[n]; }不同的二叉搜索樹 II
- 不同的二叉搜索樹 II
給定一個整數 n，生成所有由 1 ... n 為節點所組成的二叉搜索樹。
示例:
輸入: 3 輸出: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ] 解釋: 以上的輸出對應以下 5 種不同結構的二叉搜索樹： 1 3 3 2 1 / / / 3 2 1 1 3 2 / / 2 1 2 3
public List<TreeNode> generateTrees(int n) { if(n <= 0) return new ArrayList<>(); return build(1, n); } private List<TreeNode> build(int start, int end) { List<TreeNode> roots = new ArrayList<>(); if(start > end) { // null也要放入，否則下面的雙重循環進不去 roots.add(null); return roots; } if(start == end) { roots.add(new TreeNode(start)); return roots; } for(int i = start; i <= end; i++) { List<TreeNode> leftList = build(start, i - 1); List<TreeNode> rightList = build(i + 1, end); for(TreeNode left : leftList) { for(TreeNode right : rightList) { TreeNode root = new TreeNode(i); root.left = left; root.right = right; roots.add(root); } } } return roots; }驗證二叉搜索樹
- 驗證二叉搜索樹
給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。
假設一個二叉搜索樹具有如下特徵：
- 節點的左子樹只包含
小於當前節點的數。 - 節點的右子樹只包含
大於當前節點的數。 - 所有左子樹和右子樹自身必須也是二叉搜索樹。
示例 1:
輸入: 2 / 1 3 輸出: true
示例 2:
輸入: 5 / 1 4 / 3 6 輸出: false 解釋: 輸入為: [5,1,4,null,null,3,6]。 根節點的值為 5 ，但是其右子節點值為 4 。
public boolean isValidBST(TreeNode root) { // 用long型 return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean isValidBST(TreeNode root, long min, long max) { if (root == null) { return true; } if (root.val >= max || root.val <= min) { return false; } return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max); }恢復二叉搜索樹
- 恢復二叉搜索樹
二叉搜索樹中的兩個節點被錯誤地交換。
請在不改變其結構的情況下，恢復這棵樹。
示例 1:
輸入: [1,3,null,null,2] 1 / 3 2 輸出: [3,1,null,null,2] 3 / 1 2
示例 2:
輸入: [3,1,4,null,null,2] 3 / 1 4 / 2 輸出: [2,1,4,null,null,3] 2 / 1 4 / 3
進階:
- 使用 O(n) 空間複雜度的解法很容易實現。
- 你能想出一個只使用常數空間的解決方案嗎？
TreeNode first = null, second = null; TreeNode pre = new TreeNode(Integer.MIN_VALUE); public void recoverTree(TreeNode root) { if(root == null) return; robot(root); if(first != null && second != null) { int tmp = first.val; first.val = second.val; second.val = tmp; } } private void robot(TreeNode root) { if(root == null) return; robot(root.left); // 找到交換的兩個節點 if(first == null && pre.val > root.val) { first = pre; } if(first != null && pre.val > root.val) { second = root; } pre = root; robot(root.right); }修剪二叉搜索樹
- 修剪二叉搜索樹
給定一個二叉搜索樹，同時給定最小邊界L 和最大邊界 R。通過修剪二叉搜索樹，使得所有節點的值在[L, R]中 (R>=L) 。你可能需要改變樹的根節點，所以結果應當返回修剪好的二叉搜索樹的新的根節點。
示例 1:
輸入: 1 / 0 2 L = 1 R = 2 輸出: 1 2
示例 2:
輸入: 3 / 0 4 2 / 1 L = 1 R = 3 輸出: 3 / 2 / 1
public TreeNode trimBST(TreeNode root, int L, int R) { if (root == null) { return null; } if (root.val > R) { return trimBST(root.left, L, R); } if (root.val < L) { return trimBST(root.right, L, R); } root.left = trimBST(root.left, L, R); root.right = trimBST(root.right, L, R); return root; }將有序數組轉換為二叉搜索樹
- 將有序數組轉換為二叉搜索樹
將一個按照升序排列的有序數組，轉換為一棵高度平衡二叉搜索樹。
本題中，一個高度平衡二叉樹是指一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1。
示例:
給定有序數組: [-10,-3,0,5,9], 一個可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面這個高度平衡二叉搜索樹： 0 / -3 9 / / -10 5
public TreeNode sortedArrayToBST(int[] nums) { if (nums == null || nums.length == 0) { return null; } return robot(nums, 0, nums.length - 1); } private TreeNode robot(int[] nums, int start, int end) { if (start > end) { return null; } int mid = start + (end - start) / 2; TreeNode root = new TreeNode(nums[mid]); root.left = robot(nums, start, mid - 1); root.right = robot(nums, mid + 1, end); return root; }二叉搜索樹迭代器
- 二叉搜索樹迭代器
實現一個二叉搜索樹迭代器。你將使用二叉搜索樹的根節點初始化迭代器。
調用 next() 將返回二叉搜索樹中的下一個最小的數。
image
示例：
BSTIterator iterator = new BSTIterator(root); iterator.next(); // 返回 3 iterator.next(); // 返回 7 iterator.hasNext(); // 返回 true iterator.next(); // 返回 9 iterator.hasNext(); // 返回 true iterator.next(); // 返回 15 iterator.hasNext(); // 返回 true iterator.next(); // 返回 20 iterator.hasNext(); // 返回 false
提示：
- next() 和 hasNext() 操作的時間複雜度是 O(1)，並使用 O(h) 記憶體，其中 h 是樹的高度。
- 你可以假設 next() 調用總是有效的，也就是說，當調用 next() 時，BST 中至少存在一個下一個最小的數。
class BSTIterator { Stack<TreeNode> vector = new Stack<>(); TreeNode current; public BSTIterator(TreeNode root) { current = root; // 一直放入左兒子（左） while (current != null) { vector.push(current); current = current.left; } } /** @return whether we have a next smallest number */ public boolean hasNext() { return !vector.isEmpty() || current != null; } /** @return the next smallest number */ public int next() { // 一直放入左兒子（左） while (current != null) { vector.push(current); current = current.left; } int ans = 0; // 訪問當前元素（中），把右兒子入棧（右） if (!vector.isEmpty()) { current = vector.pop(); ans = current.val; current = current.right; } return ans; } } /** * Your BSTIterator object will be instantiated and called as such: * BSTIterator obj = new BSTIterator(root); * int param_1 = obj.next(); * boolean param_2 = obj.hasNext(); */二叉搜索樹中第K小的元素
- 二叉搜索樹中第K小的元素
給定一個二叉搜索樹，編寫一個函數 kthSmallest 來查找其中第 k 個最小的元素。
說明： 你可以假設 k 總是有效的，1 ≤ k ≤ 二叉搜索樹元素個數。
示例 1:
輸入: root = [3,1,4,null,2], k = 1 3 / 1 4 2 輸出: 1
示例 2:
輸入: root = [5,3,6,2,4,null,null,1], k = 3 5 / 3 6 / 2 4 / 1 輸出: 3
進階： 如果二叉搜索樹經常被修改（插入/刪除操作）並且你需要頻繁地查找第 k 小的值，你將如何優化 kthSmallest 函數？
int ans = 0; int count = 0; public int kthSmallest(TreeNode root, int k) { count = k; robot(root); return ans; } private void robot(TreeNode root) { if (root == null) { return; } robot(root.left); if (--count == 0) { ans = root.val; return; } robot(root.right); }二叉搜索樹的最近公共祖先
- 二叉搜索樹的最近公共祖先
給定一個二叉搜索樹, 找到該樹中兩個指定節點的最近公共祖先。
百度百科中最近公共祖先的定義為：「對於有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度儘可能大（一個節點也可以是它自己的祖先）。」
例如，給定如下二叉搜索樹: root = [6,2,8,0,4,7,9,null,null,3,5]
image
示例 1:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 輸出: 6 解釋: 節點 2 和節點 8 的最近公共祖先是 6。
示例 2:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 輸出: 2 解釋: 節點 2 和節點 4 的最近公共祖先是 2, 因為根據定義最近公共祖先節點可以為節點本身。
說明:
- 所有節點的值都是唯一的。
- p、q 為不同節點且均存在於給定的二叉搜索樹中。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || p == null || q == null) { return null; } TreeNode left = lowestCommonAncestor(root.left, p, q); if (root.val <= Math.max(p.val, q.val) && root.val >= Math.min(p.val, q.val)) { return root; } TreeNode right = lowestCommonAncestor(root.right, p, q); return left == null ? right : left; }刪除二叉搜索樹中的節點
- 刪除二叉搜索樹中的節點
給定一個二叉搜索樹的根節點 root 和一個值 key，刪除二叉搜索樹中的 key 對應的節點，並保證二叉搜索樹的性質不變。返回二叉搜索樹（有可能被更新）的根節點的引用。
一般來說，刪除節點可分為兩個步驟：
- 首先找到需要刪除的節點；
- 如果找到了，刪除它。
說明： 要求演算法時間複雜度為 O(h)，h 為樹的高度。
示例:
root = [5,3,6,2,4,null,7] key = 3 5 / 3 6 / 2 4 7 給定需要刪除的節點值是 3，所以我們首先找到 3 這個節點，然後刪除它。 一個正確的答案是 [5,4,6,2,null,null,7], 如下圖所示。 5 / 4 6 / 2 7 另一個正確答案是 [5,2,6,null,4,null,7]。 5 / 2 6 4 7
// todo 題目複雜，面試時不會常考，考慮忽略此題目
二叉搜索樹中的搜索
- 二叉搜索樹中的搜索
給定二叉搜索樹（BST）的根節點和一個值。 你需要在BST中找到節點值等於給定值的節點。 返回以該節點為根的子樹。 如果節點不存在，則返回 NULL。
例如，
給定二叉搜索樹: 4 / 2 7 / 1 3 和值: 2
你應該返回如下子樹:
2 / 1 3
在上述示例中，如果要找的值是 5，但因為沒有節點值為 5，我們應該返回 NULL。
public TreeNode searchBST(TreeNode root, int val) { if (root == null || root.val == val) { return root; } if (root.val < val) { return searchBST(root.right, val); } if (root.val > val) { return searchBST(root.left, val); } return null; }二叉搜索樹中的插入操作
給定二叉搜索樹（BST）的根節點和要插入樹中的值，將值插入二叉搜索樹。 返回插入後二叉搜索樹的根節點。 保證原始二叉搜索樹中不存在新值。
注意，可能存在多種有效的插入方式，只要樹在插入後仍保持為二叉搜索樹即可。 你可以返回任意有效的結果。
例如,
給定二叉搜索樹: 4 / 2 7 / 1 3 和 插入的值: 5
你可以返回這個二叉搜索樹:
4 / 2 7 / / 1 3 5
或者這個樹也是有效的:
5 / 2 7 / 1 3 4
public TreeNode insertIntoBST(TreeNode root, int val) { if (root == null) { return new TreeNode(val); } if (root.val > val) { root.left = insertIntoBST(root.left, val); } else { root.right = insertIntoBST(root.right, val); } return root; }深搜、廣搜
相同的樹
給定兩個二叉樹，編寫一個函數來檢驗它們是否相同。
如果兩個樹在結構上相同，並且節點具有相同的值，則認為它們是相同的。
示例 1:
輸入: 1 1 / / 2 3 2 3 [1,2,3], [1,2,3] 輸出: true
示例 2:
輸入: 1 1 / 2 2 [1,2], [1,null,2] 輸出: false
示例 3:
輸入: 1 1 / / 2 1 1 2 [1,2,1], [1,1,2] 輸出: false
public boolean isSameTree(TreeNode p, TreeNode q) { if (p == q) { return true; } if (p == null || q == null) { return false; } return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right); }對稱二叉樹
給定一個二叉樹，檢查它是否是鏡像對稱的。
例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的。
1 / 2 2 / / 3 4 4 3
但是下面這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的:
1 / 2 2 3 3
說明:
如果你可以運用遞歸和迭代兩種方法解決這個問題，會很加分。
遞歸
public boolean isSymmetric(TreeNode root) { return robot(root, root); } boolean robot(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } if (p == null || q == null) { return false; } return p.val == q.val && robot(p.left, q.right) && robot(p.right, q.left); }迭代
public boolean isSymmetric2(TreeNode root) { if (root == null) { return true; } Stack<TreeNode> stack = new Stack<>(); stack.push(root.left); stack.push(root.right); while (!stack.isEmpty()) { TreeNode p = stack.pop(); TreeNode q = stack.pop(); if (p == null && q == null) { continue; } if (p == null || q == null) { return false; } if (p.val != q.val) { return false; } stack.push(p.left); stack.push(q.right); stack.push(p.right); stack.push(q.left); } return true; }翻轉二叉樹
- 翻轉二叉樹
示例：
輸入：
4 / 2 7 / / 1 3 6 9
輸出：
4 / 7 2 / / 9 6 3 1
備註: 這個問題是受到 Max Howell 的 原問題 啟發的 ：
Google：我們90％的工程師使用您編寫的軟體(Homebrew)，但是您卻無法在面試時在白板上寫出翻轉二叉樹這道題，這太糟糕了。
public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } TreeNode tmp = root.left; root.left = root.right; root.right = tmp; invertTree(root.left); invertTree(root.right); return root; }二叉樹的最大深度
- 二叉樹的最大深度
給定一個二叉樹，找出其最大深度。
二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。
說明: 葉子節點是指沒有子節點的節點。
示例： 給定二叉樹 [3,9,20,null,null,15,7]，
3 / 9 20 / 15 7
返回它的最大深度 3 。
public int maxDepth(TreeNode root) { if (root == null) { return 0; } int left = maxDepth(root.left); int right = maxDepth(root.right); return left > right ? (left + 1) : (right + 1); }二叉樹的最小深度
- 二叉樹的最小深度
給定一個二叉樹，找出其最小深度。
最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。
說明: 葉子節點是指沒有子節點的節點。
示例:
給定二叉樹 [3,9,20,null,null,15,7],
3 / 9 20 / 15 7
返回它的最小深度 2.
public int minDepth(TreeNode root) { if (root == null) { return 0; } int left = minDepth(root.left); int right = minDepth(root.right); return (left == 0 || right == 0) ? (left + right + 1) : Math.min(left, right) + 1; }平衡二叉樹
- 平衡二叉樹
給定一個二叉樹，判斷它是否是高度平衡的二叉樹。
本題中，一棵高度平衡二叉樹定義為：
一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過1。
示例 1:
給定二叉樹 [3,9,20,null,null,15,7]
3 / 9 20 / 15 7
返回 true 。
示例 2:
給定二叉樹 [1,2,2,3,3,null,null,4,4]
1 / 2 2 / 3 3 / 4 4
返回 false 。
public boolean isBalanced(TreeNode root) { if (root == null) { return true; } return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right); } int depth(TreeNode node) { if (node == null) { return 0; } return Math.max(depth(node.left), depth(node.right)) + 1; }完全二叉樹的節點個數
給出一個完全二叉樹，求出該樹的節點個數。
說明：
完全二叉樹的定義如下：在完全二叉樹中，除了最底層節點可能沒填滿外，其餘每層節點數都達到最大值，並且最下面一層的節點都集中在該層最左邊的若干位置。若最底層為第 h 層，則該層包含 1~ 2^h 個節點。
示例:
輸入:
1 / 2 3 / / 4 5 6 輸出: 6
public int countNodes(TreeNode root) { if (root == null) { return 0; } int left = 0; int right = 0; TreeNode p = root; while (p != null) { p = p.left; left++; } p = root; while (p != null) { p = p.right; right++; } if (left == right) { return (1 << left) - 1; } return countNodes(root.left) + countNodes(root.right) + 1; }二叉樹最大寬度
- 二叉樹最大寬度
給定一個二叉樹，編寫一個函數來獲取這個樹的最大寬度。樹的寬度是所有層中的最大寬度。這個二叉樹與 滿二叉樹（full binary tree） 結構相同，但一些節點為空。
每一層的寬度被定義為兩個端點（該層最左和最右的非空節點，兩端點間的null節點也計入長度）之間的長度。
示例 1:
輸入: 1 / 3 2 / 5 3 9 輸出: 4 解釋: 最大值出現在樹的第 3 層，寬度為 4 (5,3,null,9)。
示例 2:
輸入: 1 / 3 / 5 3 輸出: 2 解釋: 最大值出現在樹的第 3 層，寬度為 2 (5,3)。
示例 3:
輸入: 1 / 3 2 / 5 輸出: 2 解釋: 最大值出現在樹的第 2 層，寬度為 2 (3,2)。
示例 4:
輸入: 1 / 3 2 / 5 9 / 6 7 輸出: 8 解釋: 最大值出現在樹的第 4 層，寬度為 8 (6,null,null,null,null,null,null,7)。
注意: 答案在32位有符號整數的表示範圍內。
public int widthOfBinaryTree(TreeNode root) { int[] ans = new int[1]; robot(root, ans, new ArrayList<>(), 0, 1); return ans[0]; } private void robot(TreeNode root, int[] ans, ArrayList<Integer> leftIndexes, int level, int index) { if (root == null) { return; } if (leftIndexes.size() <= level) { leftIndexes.add(index); } ans[0] = Math.max(ans[0], index - leftIndexes.get(level) + 1); robot(root.left, ans, leftIndexes, level + 1, 2 * index); robot(root.right, ans, leftIndexes, level + 1, 2 * index + 1); }二叉樹的直徑
- 二叉樹的直徑
給定一棵二叉樹，你需要計算它的直徑長度。一棵二叉樹的直徑長度是任意兩個結點路徑長度中的最大值。這條路徑可能穿過根結點。
示例 : 給定二叉樹
1 / 2 3 / 4 5
返回 3, 它的長度是路徑 [4,2,1,3] 或者 [5,2,1,3]。
注意：兩結點之間的路徑長度是以它們之間邊的數目表示。
public int diameterOfBinaryTree(TreeNode root) { int[] ans = new int[1]; robot(root, ans); return ans[0]; } private int robot(TreeNode root, int[] ans) { if (root == null) { return 0; } int left = robot(root.left, ans); int right = robot(root.right, ans); // 維護直徑最大值 ans[0] = Math.max(left + right, ans[0]); // 返回當前節點的最大直徑 return Math.max(left, right) + 1; }二叉樹的坡度
- 二叉樹的坡度
給定一個二叉樹，計算整個樹的坡度。
一個樹的節點的坡度定義即為，該節點左子樹的結點之和和右子樹結點之和的差的絕對值。空結點的的坡度是0。
整個樹的坡度就是其所有節點的坡度之和。
示例:
輸入: 1 / 2 3 輸出: 1 解釋: 結點的坡度 2 : 0 結點的坡度 3 : 0 結點的坡度 1 : |2-3| = 1 樹的坡度 : 0 + 0 + 1 = 1
注意:
- 任何子樹的結點的和不會超過32位整數的範圍。
- 坡度的值不會超過32位整數的範圍。
public int findTilt(TreeNode root) { int[] ans = new int[1]; robot(root, ans); return ans[0]; } private int robot(TreeNode root, int[] ans) { if (root == null) { return 0; } int left = robot(root.left, ans); int right = robot(root.right, ans); ans[0] += Math.abs(left - right); return left + right + root.val; }二叉樹的所有路徑
- 二叉樹的所有路徑
給定一個二叉樹，返回所有從根節點到葉子節點的路徑。
說明: 葉子節點是指沒有子節點的節點。
示例:
輸入: 1 / 2 3 5 輸出: ["1->2->5", "1->3"] 解釋: 所有根節點到葉子節點的路徑為: 1->2->5, 1->3
public List<String> binaryTreePaths(TreeNode root) { List<String> ans = new ArrayList<>(); robot(root, ans, ""); return ans; } private void robot(TreeNode root, List<String> ans, String path) { if (root == null) { return; } if (root.left == null && root.right == null) { ans.add(path + root.val); return; } robot(root.left, ans, path + root.val + "->"); robot(root.right, ans, path + root.val + "->"); }二叉樹的最近公共祖先
- 二叉樹的最近公共祖先
給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。
百度百科中最近公共祖先的定義為：「對於有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度儘可能大（一個節點也可以是它自己的祖先）。」
例如，給定如下二叉樹: root = [3,5,1,6,2,0,8,null,null,7,4]
image
示例 1:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 輸出: 3 解釋: 節點 5 和節點 1 的最近公共祖先是節點 3。
示例 2:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 輸出: 5 解釋: 節點 5 和節點 4 的最近公共祖先是節點 5。因為根據定義最近公共祖先節點可以為節點本身。
說明:
- 所有節點的值都是唯一的。
- p、q 為不同節點且均存在於給定的二叉樹中。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || 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 root; } return left == null ? right : left; }最深葉節點的最近公共祖先
- 最深葉節點的最近公共祖先
給你一個有根節點的二叉樹，找到它最深的葉節點的最近公共祖先。
回想一下：
- 葉節點 是二叉樹中沒有子節點的節點
- 樹的根節點的 深度 為 0，如果某一節點的深度為 d，那它的子節點的深度就是 d+1
- 如果我們假定 A 是一組節點 S 的 最近公共祖先 中的每個節點都在以 A 為根節點的子樹中，且 A 的深度達到此條件下可能的最大值。
示例 1：
輸入：root = [1,2,3] 輸出：[1,2,3]
示例 2：
輸入：root = [1,2,3,4] 輸出：[4]
示例 3：
輸入：root = [1,2,3,4,5] 輸出：[2,4,5]
提示：
- 給你的樹中將有 1 到 1000 個節點。
- 樹中每個節點的值都在 1 到 1000 之間。
public TreeNode lcaDeepestLeaves(TreeNode root) { if (root == null) { return null; } int left = depth(root.left); int right = depth(root.right); if (left == right) { return root; } return left > right ? lcaDeepestLeaves(root.left) : lcaDeepestLeaves(root.right); } private int depth(TreeNode root) { if (root == null) { return 0; } int left = depth(root.left); int right = depth(root.right); return Math.max(left, right) + 1; }路徑和
左葉子之和
- 左葉子之和
計算給定二叉樹的所有左葉子之和。
示例：
3 / 9 20 / 15 7
在這個二叉樹中，有兩個左葉子，分別是 9 和 15，所以返回 24
public int sumOfLeftLeaves(TreeNode root) { int[] ans = new int[1]; robot(root, ans, false); return ans[0]; } private void robot(TreeNode root, int[] ans, boolean isLeft) { if (root == null) { return; } if (root.left == null && root.right == null && isLeft) { ans[0] += root.val; } robot(root.left, ans, true); robot(root.right, ans, false); }路徑總和
- 路徑總和
給定一個二叉樹和一個目標和，判斷該樹中是否存在根節點到葉子節點的路徑，這條路徑上所有節點值相加等於目標和。
說明: 葉子節點是指沒有子節點的節點。
示例: 給定如下二叉樹，以及目標和 sum = 22，
5 / 4 8 / / 11 13 4 / 7 2 1
返回 true, 因為存在目標和為 22 的根節點到葉子節點的路徑 5->4->11->2。
public boolean hasPathSum(TreeNode root, int sum) { if (root == null) { return false; } // 葉子節點 && 和為 sum if (root.left == null && root.right == null && sum - root.val == 0) { return true; } return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); }路徑總和 II
- 路徑總和 II
給定一個二叉樹和一個目標和，找到所有從根節點到葉子節點路徑總和等於給定目標和的路徑。
說明: 葉子節點是指沒有子節點的節點。
示例: 給定如下二叉樹，以及目標和 sum = 22，
5 / 4 8 / / 11 13 4 / / 7 2 5 1
返回:
[ [5,4,11,2], [5,8,4,5] ]
public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> ans = new ArrayList<>(); robot(root, sum, ans, new ArrayList<>()); return ans; } private void robot(TreeNode root, int sum, List<List<Integer>> ans, List<Integer> tmp) { if (root == null) { return; } tmp.add(root.val); if (root.left == null && root.right == null && sum == root.val) { ans.add(new ArrayList(tmp)); tmp.remove(tmp.size() - 1); return; } robot(root.left, sum - root.val, ans, tmp); robot(root.right, sum - root.val, ans, tmp); tmp.remove(tmp.size() - 1); }路徑總和 III
- 路徑總和 III
給定一個二叉樹，它的每個結點都存放著一個整數值。
找出路徑和等於給定數值的路徑總數。
路徑不需要從根節點開始，也不需要在葉子節點結束，但是路徑方向必須是向下的（只能從父節點到子節點）。
二叉樹不超過1000個節點，且節點數值範圍是 [-1000000,1000000] 的整數。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10 / 5 -3 / 3 2 11 / 3 -2 1
返回 3。和等於 8 的路徑有:
1. 5 -> 3 2. 5 -> 2 -> 1 3. -3 -> 11
public int pathSum(TreeNode root, int sum) { if (root == null) { return 0; } return robot(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum); } private int robot(TreeNode root, int sum) { if (root == null) { return 0; } int ans = 0; sum -= root.val; if (sum == 0) { ans++; } ans += robot(root.left, sum); ans += robot(root.right, sum); return ans; }二叉樹中的最大路徑和
- 二叉樹中的最大路徑和
給定一個非空二叉樹，返回其最大路徑和。
本題中，路徑被定義為一條從樹中任意節點出發，達到任意節點的序列。該路徑至少包含一個節點，且不一定經過根節點。
示例 1:
輸入: [1,2,3] 1 / 2 3 輸出: 6
示例 2:
輸入: [-10,9,20,null,null,15,7] -10 / 9 20 / 15 7 輸出: 42
public int maxPathSum(TreeNode root) { int[] ans = new int[] { Integer.MIN_VALUE }; robot(root, ans); return ans[0]; } private int robot(TreeNode root, int[] ans) { if (root == null) { return 0; } int left = robot(root.left, ans); int right = robot(root.right, ans); int res = root.val; if (Math.max(left, right) > 0) { res += Math.max(left, right); } int gain = Math.max(Math.max(left, right), left + right); ans[0] = Math.max(ans[0], root.val); ans[0] = Math.max(ans[0], root.val + gain); return res; }求根到葉子節點數字之和
- 求根到葉子節點數字之和
給定一個二叉樹，它的每個結點都存放一個 0-9 的數字，每條從根到葉子節點的路徑都代表一個數字。
例如，從根到葉子節點路徑 1->2->3 代表數字 123。
計算從根到葉子節點生成的所有數字之和。
說明: 葉子節點是指沒有子節點的節點。
示例 1:
輸入: [1,2,3] 1 / 2 3 輸出: 25 解釋: 從根到葉子節點路徑 1->2 代表數字 12. 從根到葉子節點路徑 1->3 代表數字 13. 因此，數字總和 = 12 + 13 = 25.
示例 2:
輸入: [4,9,0,5,1] 4 / 9 0 / 5 1 輸出: 1026 解釋: 從根到葉子節點路徑 4->9->5 代表數字 495. 從根到葉子節點路徑 4->9->1 代表數字 491. 從根到葉子節點路徑 4->0 代表數字 40. 因此，數字總和 = 495 + 491 + 40 = 1026.
public int sumNumbers(TreeNode root) { return robot(root, 0); } private int robot(TreeNode root, int p) { if (root == null) { return 0; } p = p * 10 + root.val; if (root.left == null && root.right == null) { return p; } return robot(root.left, p) + robot(root.right, p); }序列化二叉樹、構造二叉樹
從前序與中序遍歷序列構造二叉樹
- 從前序與中序遍歷序列構造二叉樹
根據一棵樹的前序遍歷與中序遍歷構造二叉樹。
注意: 你可以假設樹中沒有重複的元素。
例如，給出
前序遍歷 preorder = [3,9,20,15,7] 中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹：
3 / 9 20 / 15 7
public TreeNode buildTree(int[] pre, int[] in) { return robot(pre, in, 0, 0, in.length - 1); } private TreeNode robot(int[] pre, int[] in, int preStart, int inStart, int inEnd) { if (preStart >= pre.length || inStart > inEnd) { return null; } // 找到pos TreeNode root = new TreeNode(pre[preStart]); int index = 0; for (int i = inStart; i <= inEnd; i++) { if (in[i] == root.val) { index = i; break; } } root.left = robot(pre, in, preStart + 1, inStart, index - 1); root.right = robot(pre, in, preStart + 1 + index - inStart, index + 1, inEnd); return root; }從中序與後序遍歷序列構造二叉樹
- 從中序與後序遍歷序列構造二叉樹
根據一棵樹的中序遍歷與後序遍歷構造二叉樹。
注意: 你可以假設樹中沒有重複的元素。
例如，給出
中序遍歷 inorder = [9,3,15,20,7] 後序遍歷 postorder = [9,15,7,20,3]
返回如下的二叉樹：
3 / 9 20 / 15 7
public TreeNode buildTree(int[] in, int[] post) { return robot(in, post, 0, in.length - 1, 0, post.length - 1); } private TreeNode robot(int[] in, int[] post, int inStart, int inEnd, int postStart, int postEnd) { if (postStart > postEnd) { return null; } TreeNode root = new TreeNode(post[postEnd]); int pos = 0; // 找到pos for (int i = inStart; i <= inEnd; i++) { if (in[i] == root.val) { pos = i; break; } } root.left = robot(in, post, inStart, pos - 1, postStart, postStart + pos - inStart - 1); root.right = robot(in, post, pos + 1, inEnd, postEnd + pos - inEnd, postEnd - 1); return root; }先序遍歷構造二叉樹
- 先序遍歷構造二叉樹
返回與給定先序遍歷 preorder 相匹配的二叉搜索樹（binary search tree）的根結點。
(回想一下，二叉搜索樹是二叉樹的一種，其每個節點都滿足以下規則，對於 node.left 的任何後代，值總 < node.val，而 node.right 的任何後代，值總 > node.val。此外，先序遍歷首先顯示節點的值，然後遍歷 node.left，接著遍歷 node.right。）
示例：
輸入：[8,5,1,7,10,12] 輸出：[8,5,10,1,7,null,12]
image
@w=400
提示：
- 1 <= preorder.length <= 100
- 先序 preorder 中的值是不同的。
int index = 0; public TreeNode bstFromPreorder(int[] preorder) { return robot(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE); } private TreeNode robot(int[] preorder, int min, int max) { if (index == preorder.length) { return null; } int val = preorder[index]; if (val < min || val > max) { return null; } index++; TreeNode root = new TreeNode(val); root.left = robot(preorder, min, val); root.right = robot(preorder, val, max); return root; }序列化和反序列化二叉搜索樹
- 序列化和反序列化二叉搜索樹
序列化是將數據結構或對象轉換為一系列位的過程，以便它可以存儲在文件或記憶體緩衝區中，或通過網路連接鏈路傳輸，以便稍後在同一個或另一個電腦環境中重建。
設計一個演算法來序列化和反序列化二叉搜索樹。 對序列化/反序列化演算法的工作方式沒有限制。 您只需確保二叉搜索樹可以序列化為字元串，並且可以將該字元串反序列化為最初的二叉搜索樹。
編碼的字元串應儘可能緊湊。
注意：不要使用類成員/全局/靜態變數來存儲狀態。 你的序列化和反序列化演算法應該是無狀態的。
public class Codec { // Encodes a tree to a single string. // BST 的前序遍歷 public String serialize(TreeNode root) { if (root == null) { return ""; } StringBuilder sb = new StringBuilder(); robot(root, sb); return sb.substring(0, sb.length() - 1); } private void robot(TreeNode root, StringBuilder sb) { if (root == null) { return; } sb.append(root.val).append(","); robot(root.left, sb); robot(root.right, sb); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if (data == null || Objects.equals(data, "")) { return null; } String[] pre = data.split(","); return build(pre, 0, pre.length - 1); } private TreeNode build(String[] pre, int start, int end) { if (start > end) { return null; } TreeNode root = new TreeNode(Integer.valueOf(pre[start])); // 找到對應的 index int index = end + 1; for (int i = start + 1; i <= end; i++) { if (Integer.valueOf(pre[i]) > root.val) { index = i; break; } } root.left = build(pre, start + 1, index - 1); root.right = build(pre, index, end); return root; } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.deserialize(codec.serialize(root));二叉樹的序列化與反序列化
- 二叉樹的序列化與反序列化
序列化是將一個數據結構或者對象轉換為連續的比特位的操作，進而可以將轉換後的數據存儲在一個文件或者記憶體中，同時也可以通過網路傳輸到另一個電腦環境，採取相反方式重構得到原數據。
請設計一個演算法來實現二叉樹的序列化與反序列化。這裡不限定你的序列 / 反序列化演算法執行邏輯，你只需要保證一個二叉樹可以被序列化為一個字元串並且將這個字元串反序列化為原始的樹結構。
示例:
你可以將以下二叉樹： 1 / 2 3 / 4 5 序列化為 "[1,2,3,null,null,4,5]"
提示: 這與 LeetCode 目前使用的方式一致，詳情請參閱 LeetCode 序列化二叉樹的格式。你並非必須採取這種方式，你也可以採用其他的方法解決這個問題。
說明: 不要使用類的成員 / 全局 / 靜態變數來存儲狀態，你的序列化和反序列化演算法應該是無狀態的。
public String serialize(TreeNode root) { if (root == null) { return ""; } StringBuilder sb = new StringBuilder(); Deque<TreeNode> deque = new LinkedList<>(); deque.add(root); while (!deque.isEmpty()) { TreeNode p = deque.pop(); if (p == null) { sb.append(",#"); } else { sb.append(",").append(p.val); deque.add(p.left); deque.add(p.right); } } return sb.toString().substring(1); } public TreeNode deserialize(String data) { if (data == null || Objects.equals(data, "")) { return null; } String[] s = data.split(","); TreeNode[] root = new TreeNode[s.length]; for (int i = 0; i < root.length; i++) { if (!Objects.equals(s[i], "#")) { root[i] = new TreeNode(Integer.valueOf(s[i])); } } int parent = 0; for (int i = 0; parent * 2 + 2 < s.length; i++) { if (root[i] != null) { root[i].left = root[parent * 2 + 1]; root[i].right = root[parent * 2 + 2]; parent++; } } return root[0]; }
