公眾號(hào)
coding 筆記、點(diǎn)滴記錄，以后的文章也會(huì)同步到公眾號(hào)（Coding Insight）中，希望大家關(guān)注_
題解
本文中所有題解，都在 https://github.com/LjyYano/LeetCode/tree/master/leetcode/src/main/java
LeetCode 樹(shù)的定義
二叉樹(shù)
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
N叉樹(shù)
public class Node {
public int val;
public List<Node> children;
public Node() {
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
}
二叉樹(shù)遍歷
二叉樹(shù)最基本的遍歷方式就是：前序遍歷、中序遍歷和后序遍歷。
- 前序遍歷首先訪問(wèn)根節(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。
- 中序遍歷是先遍歷左子樹(shù)，然后訪問(wèn)根節(jié)點(diǎn)，然后遍歷右子樹(shù)。
- 后序遍歷是先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)樹(shù)的根節(jié)點(diǎn)。
簡(jiǎn)單概況如下：
- 前序遍歷：根左右
- 中序遍歷：左根右
- 后序遍歷：左右根
TIPS：前中后序遍歷區(qū)別在于三字中的中間那個(gè)字，前、中、后序分別對(duì)應(yīng)左、根、右。
二叉樹(shù)前序遍歷
- 二叉樹(shù)的前序遍歷
給定一個(gè)二叉樹(shù)，返回它的 前序 遍歷。
示例:
輸入: [1,null,2,3]
1
\
2
/
3
輸出: [1,2,3]
進(jìn)階: 遞歸算法很簡(jiǎn)單，你可以通過(guò)迭代算法完成嗎？
遞歸
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);
}
迭代
迭代步驟：
- 從根節(jié)點(diǎn)開(kāi)始，每次迭代彈出當(dāng)前棧頂元素
- 將其孩子節(jié)點(diǎn)壓入棧中（先壓右孩子再壓左孩子）
public List<Integer> preorderTraversal2(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
// 將根節(jié)點(diǎn)入棧
stack.push(root);
while (!stack.isEmpty()) {
// 取出棧頂元素
TreeNode tmp = stack.pop();
if (tmp != null) {
ans.add(tmp.val);
// 將其孩子節(jié)點(diǎn)壓入棧中（先右節(jié)點(diǎn)、再左節(jié)點(diǎn)）
stack.add(tmp.right);
stack.add(tmp.left);
}
}
return ans;
}
算法復(fù)雜度:
- 時(shí)間復(fù)雜度：樹(shù)中每個(gè)節(jié)點(diǎn)都遍歷一次，因此時(shí)間復(fù)雜度為 O(N)，其中 N 為樹(shù)中節(jié)點(diǎn)的數(shù)量。
- 空間復(fù)雜度：
- 最壞情況：樹(shù)為鏈表，樹(shù)的高度=樹(shù)的節(jié)點(diǎn)個(gè)數(shù)，此時(shí)空間復(fù)雜度是 O(N)。
- 最好情況：樹(shù)高度平衡，此時(shí)空間復(fù)雜度是 O(logn)。
二叉樹(shù)中序遍歷
- 二叉樹(shù)的中序遍歷
給定一個(gè)二叉樹(shù)，返回它的 中序 遍歷。
示例:
輸入: [1,null,2,3]
1
\
2
/
3
輸出: [1,3,2]
進(jìn)階: 遞歸算法很簡(jiǎn)單，你可以通過(guò)迭代算法完成嗎？
遞歸
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;
}
// 訪問(wèn)當(dāng)前元素（根），把右兒子入棧（右）
if (!stack.isEmpty()) {
root = stack.pop();
ans.add(root.val);
root = root.right;
}
}
return ans;
}
算法復(fù)雜度
- 時(shí)間復(fù)雜度：O(n)。遞歸函數(shù) T(n) = 2?T(n/2)+1。
- 空間復(fù)雜度：最壞情況下需要空間O(n)，平均情況為O(logn)。
二叉樹(shù)后序遍歷
- 二叉樹(shù)的后序遍歷
給定一個(gè)二叉樹(shù)，返回它的 后序 遍歷。
示例:
輸入: [1,null,2,3]
1
\
2
/
3
輸出: [3,2,1]
進(jìn)階: 遞歸算法很簡(jiǎn)單，你可以通過(guò)迭代算法完成嗎？
遞歸
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);
}
后序遍歷的非遞歸寫(xiě)法有些麻煩，因?yàn)楣?jié)點(diǎn)第一次訪問(wèn)時(shí)并不打印，而是在第二次遍歷時(shí)才打印。所以需要一個(gè)變量來(lái)標(biāo)記該結(jié)點(diǎn)是否訪問(wèn)過(guò)。
迭代：利用輔助類
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;
}
算法復(fù)雜度：
- 時(shí)間復(fù)雜度：訪問(wèn)每個(gè)節(jié)點(diǎn)恰好一次，因此時(shí)間復(fù)雜度為 O(N)，其中 N 是節(jié)點(diǎn)的個(gè)數(shù)，也就是樹(shù)的大小。
- 空間復(fù)雜度：取決于樹(shù)的結(jié)構(gòu)，最壞情況需要保存整棵樹(shù)，因此空間復(fù)雜度為 O(N)。
二叉樹(shù)的層次遍歷
- 二叉樹(shù)的層次遍歷
給定一個(gè)二叉樹(shù)，返回其按層次遍歷的節(jié)點(diǎn)值。 （即逐層地，從左到右訪問(wèn)所有節(jié)點(diǎn)）。
例如：給定二叉樹(shù): [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其層次遍歷結(jié)果：
[
[3],
[9,20],
[15,7]
]
遞歸
首先確認(rèn)樹(shù)非空，然后調(diào)用遞歸函數(shù) helper(node, level)，參數(shù)是當(dāng)前節(jié)點(diǎn)和節(jié)點(diǎn)的層次。
算法過(guò)程:
- ans 為結(jié)果列表，level 為當(dāng)前遍歷的層數(shù)（初始為0）
- 若 ans 的長(zhǎng)度 = level，向 ans 增加一個(gè)空列表
- 將節(jié)點(diǎn)值放入 ans 的第 level 個(gè)列表結(jié)尾
- 遍歷左右子節(jié)點(diǎn)，此時(shí) 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);
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(N)，因?yàn)槊總€(gè)節(jié)點(diǎn)恰好會(huì)被運(yùn)算一次。
- 空間復(fù)雜度：O(N)，保存輸出結(jié)果的數(shù)組包含 N 個(gè)節(jié)點(diǎn)的值。
迭代
算法過(guò)程：
第 0 層只包含根節(jié)點(diǎn) root ，算法實(shí)現(xiàn)如下：
- 初始化隊(duì)列只包含一個(gè)節(jié)點(diǎn) root 和層次編號(hào) 0 ： level = 0。
- 當(dāng)隊(duì)列非空的時(shí)候：
- 新建一個(gè)空列表，表示當(dāng)前層結(jié)果 current。
- 計(jì)算當(dāng)前層有多少個(gè)元素：等于隊(duì)列的長(zhǎng)度。
- 將這些元素從隊(duì)列中彈出，并加入 current 列表中。
- 將他們的孩子節(jié)點(diǎn)作為下一層壓入隊(duì)列中。
- 將 當(dāng)前層結(jié)果 current 放入 ans 中。
- 進(jìn)入下一層循環(huán)。
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<>();
// 當(dāng)前層的元素個(gè)數(shù)
int length = queue.size();
for (int i = 0; i < length; ++i) {
TreeNode node = queue.remove();
// 放入結(jié)果
current.add(node.val);
// 依次將 node 的左右子節(jié)點(diǎn)加入隊(duì)列
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
ans.add(current);
}
return ans;
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(N)，因?yàn)槊總€(gè)節(jié)點(diǎn)恰好會(huì)被運(yùn)算一次。
- 空間復(fù)雜度：O(N)，保存輸出結(jié)果的數(shù)組包含 N 個(gè)節(jié)點(diǎn)的值。
二叉樹(shù)的右視圖
- 二叉樹(shù)的右視圖
給定一棵二叉樹(shù)，想象自己站在它的右側(cè)，按照從頂部到底部的順序，返回從右側(cè)所能看到的節(jié)點(diǎn)值。
示例:
輸入: [1,2,3,null,5,null,4]
輸出: [1, 3, 4]
解釋:
1 <---
/ \
2 3 <---
\ \
5 4 <---
本題是層序遍歷的變種，層序遍歷是存儲(chǔ)二叉樹(shù)每行的每個(gè)元素，而本題僅存儲(chǔ)二叉樹(shù)每行的最后一個(gè)元素。
遞歸
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 是一個(gè) 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;
// 當(dāng)前層的元素個(gè)數(shù)
int length = queue.size();
for (int i = 0; i < length; ++i) {
TreeNode node = queue.remove();
// 放入結(jié)果
current = node.val;
// 依次將 node 的左右子節(jié)點(diǎn)加入隊(duì)列
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
ans.add(current);
}
return ans;
}
在每個(gè)樹(shù)行中找最大值
- 在每個(gè)樹(shù)行中找最大值
您需要在二叉樹(shù)的每一行中找到最大的值。
示例：
輸入:
1
/ \
3 2
/ \ \
5 3 9
輸出: [1, 3, 9]
本題也是層序遍歷的變種，層序遍歷是存儲(chǔ)二叉樹(shù)每行的每個(gè)元素，而本題僅存儲(chǔ)二叉樹(shù)每行的最大元素。
遞歸
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;
// 當(dāng)前層的元素個(gè)數(shù)
int length = queue.size();
for (int i = 0; i < length; ++i) {
TreeNode node = queue.remove();
// 放入結(jié)果（變化的地方）
current = Math.max(current, node.val);
// 依次將 node 的左右子節(jié)點(diǎn)加入隊(duì)列
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
ans.add(current);
}
return ans;
}
二叉樹(shù)的垂序遍歷
- 二叉樹(shù)的垂序遍歷
給定二叉樹(shù)，按垂序遍歷返回其結(jié)點(diǎn)值。
對(duì)位于 (X, Y) 的每個(gè)結(jié)點(diǎn)而言，其左右子結(jié)點(diǎn)分別位于 (X-1, Y-1) 和 (X+1, Y-1)。
把一條垂線從 X = -infinity 移動(dòng)到 X = +infinity ，每當(dāng)該垂線與結(jié)點(diǎn)接觸時(shí)，我們按從上到下的順序報(bào)告結(jié)點(diǎn)的值（ Y 坐標(biāo)遞減）。
如果兩個(gè)結(jié)點(diǎn)位置相同，則首先報(bào)告的結(jié)點(diǎn)值較小。
按 X 坐標(biāo)順序返回非空?qǐng)?bào)告的列表。每個(gè)報(bào)告都有一個(gè)結(jié)點(diǎn)值列表。
示例 1：
輸入：[3,9,20,null,null,15,7]
輸出：[[9],[3,15],[20],[7]]
解釋：
在不喪失其普遍性的情況下，我們可以假設(shè)根結(jié)點(diǎn)位于 (0, 0)：
然后，值為 9 的結(jié)點(diǎn)出現(xiàn)在 (-1, -1)；
值為 3 和 15 的兩個(gè)結(jié)點(diǎn)分別出現(xiàn)在 (0, 0) 和 (0, -2)；
值為 20 的結(jié)點(diǎn)出現(xiàn)在 (1, -1)；
值為 7 的結(jié)點(diǎn)出現(xiàn)在 (2, -2)。
示例 2：
@w=400
輸入：[1,2,3,4,5,6,7]
輸出：[[4],[2],[1,5,6],[3],[7]]
解釋：
根據(jù)給定的方案，值為 5 和 6 的兩個(gè)結(jié)點(diǎn)出現(xiàn)在同一位置。
然而，在報(bào)告 "[1,5,6]" 中，結(jié)點(diǎn)值 5 排在前面，因?yàn)?5 小于 6。
提示：
樹(shù)的結(jié)點(diǎn)數(shù)介于 1 和 1000 之間。
每個(gè)結(jié)點(diǎn)值介于 0 和 1000 之間。
解題思路
設(shè)根節(jié)點(diǎn)的(x,y)=(0,0)，對(duì)于節(jié)點(diǎn)坐標(biāo)(x,y)，其左節(jié)點(diǎn)坐標(biāo)為(x-1,y-1)，右節(jié)點(diǎn)坐標(biāo)為(x+1,y-1)。
- 構(gòu)造 List<PositionNode> posNodes，遍歷二叉樹(shù)每個(gè)節(jié)點(diǎn)，填入 PositionNode 的 x 坐標(biāo)、y 坐標(biāo)、val 值。
- 將 posNodes 展開(kāi)成 key 是 x 坐標(biāo)、value 是對(duì)應(yīng) PositionNode 的 positionMap，注意這里使用 TreeMap，因?yàn)橐獙?duì) x 坐標(biāo)排序。
- 構(gòu)建結(jié)果 ans：遍歷 positionMap，相同位置節(jié)點(diǎn)，按照自然順序排序（即先按照 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) {
// 構(gòu)建節(jié)點(diǎn)的位置信息
List<PositionNode> posNodes = new ArrayList<>();
robot(root, posNodes, 0, 0);
// 將 posNodes 展開(kāi)成 key 是 x 坐標(biāo)、value 是對(duì)應(yīng) PositionNode 的 map
// 注意這里使用 TreeMap，因?yàn)橐獙?duì) x 坐標(biāo)排序
Map<Integer, List<PositionNode>> positionMap = posNodes.stream().collect(
Collectors.groupingBy(PositionNode::getX, TreeMap::new, Collectors.toList()));
// 構(gòu)建結(jié)果
List<List<Integer>> ans = new ArrayList<>();
positionMap.forEach((k, v) -> {
// 題目要求：相同位置節(jié)點(diǎn)，按照自然順序排序（即先按照 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));
// 根節(jié)點(diǎn)的(x,y)=(0,0)，若某個(gè)節(jié)點(diǎn)坐標(biāo)為(x,y)，則左節(jié)點(diǎn)坐標(biāo)為(x-1,y-1)，右節(jié)點(diǎn)坐標(biāo)為(x+1,y-1)
robot(root.left, posNodes, x - 1, y - 1);
robot(root.right, posNodes, x + 1, y - 1);
}
二叉樹(shù)的鋸齒形層次遍歷
- 二叉樹(shù)的鋸齒形層次遍歷
給定一個(gè)二叉樹(shù)，返回其節(jié)點(diǎn)值的鋸齒形層次遍歷。（即先從左往右，再?gòu)挠彝筮M(jìn)行下一層遍歷，以此類推，層與層之間交替進(jìn)行）。
例如：
給定二叉樹(shù) [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回鋸齒形層次遍歷如下：
[
[3],
[20,9],
[15,7]
]
本題是層序遍歷的變種，僅需將層序遍歷的偶數(shù)行逆序即可。
遞歸
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<>();
// 當(dāng)前層的元素個(gè)數(shù)
int length = queue.size();
for (int i = 0; i < length; ++i) {
TreeNode node = queue.remove();
// 放入結(jié)果
current.add(node.val);
// 依次將 node 的左右子節(jié)點(diǎn)加入隊(duì)列
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 叉樹(shù)遍歷
N叉樹(shù)的層序遍歷
- N叉樹(shù)的層序遍歷
給定一個(gè) N 叉樹(shù)，返回其節(jié)點(diǎn)值的層序遍歷。 (即從左到右，逐層遍歷)。
例如，給定一個(gè) 3叉樹(shù) :
@w=400
返回其層序遍歷:
[
[1],
[3,2,4],
[5,6]
]
說(shuō)明:
- 樹(shù)的深度不會(huì)超過(guò) 1000。
- 樹(shù)的節(jié)點(diǎn)總數(shù)不會(huì)超過(guò) 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叉樹(shù)的前序遍歷
- N叉樹(shù)的前序遍歷
給定一個(gè) N 叉樹(shù)，返回其節(jié)點(diǎn)值的前序遍歷。
例如，給定一個(gè) 3叉樹(shù) :
@w=400
返回其前序遍歷: [1,3,5,6,2,4]。
說(shuō)明: 遞歸法很簡(jiǎn)單，你可以使用迭代法完成此題嗎？
遞歸
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叉樹(shù)的后序遍歷
- N叉樹(shù)的后序遍歷
給定一個(gè) N 叉樹(shù)，返回其節(jié)點(diǎn)值的后序遍歷。
例如，給定一個(gè) 3叉樹(shù) :
@w=400
返回其后序遍歷: [5,6,3,2,4,1].
說(shuō)明: 遞歸法很簡(jiǎn)單，你可以使用迭代法完成此題嗎?
遞歸
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);
}
迭代
// 后續(xù)遍歷：左右中
// 迭代順序：中右左
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;
}
二叉搜索樹(shù)
不同的二叉搜索樹(shù)
- 不同的二叉搜索樹(shù)
給定一個(gè)整數(shù) n，求以 1 ... n 為節(jié)點(diǎn)組成的二叉搜索樹(shù)有多少種？
示例:
輸入: 3
輸出: 5
解釋:
給定 n = 3, 一共有 5 種不同結(jié)構(gòu)的二叉搜索樹(shù):
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];
}
不同的二叉搜索樹(shù) II
- 不同的二叉搜索樹(shù) II
給定一個(gè)整數(shù) n，生成所有由 1 ... n 為節(jié)點(diǎn)所組成的二叉搜索樹(shù)。
示例:
輸入: 3
輸出:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解釋:
以上的輸出對(duì)應(yīng)以下 5 種不同結(jié)構(gòu)的二叉搜索樹(shù)：
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也要放入，否則下面的雙重循環(huán)進(jìn)不去
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;
}
驗(yàn)證二叉搜索樹(shù)
- 驗(yàn)證二叉搜索樹(shù)
給定一個(gè)二叉樹(shù)，判斷其是否是一個(gè)有效的二叉搜索樹(shù)。
假設(shè)一個(gè)二叉搜索樹(shù)具有如下特征：
- 節(jié)點(diǎn)的左子樹(shù)只包含
小于當(dāng)前節(jié)點(diǎn)的數(shù)。 - 節(jié)點(diǎn)的右子樹(shù)只包含
大于當(dāng)前節(jié)點(diǎn)的數(shù)。 - 所有左子樹(shù)和右子樹(shù)自身必須也是二叉搜索樹(shù)。
示例 1:
輸入:
2
/ \
1 3
輸出: true
示例 2:
輸入:
5
/ \
1 4
/ \
3 6
輸出: false
解釋: 輸入為: [5,1,4,null,null,3,6]。
根節(jié)點(diǎn)的值為 5 ，但是其右子節(jié)點(diǎn)值為 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);
}
恢復(fù)二叉搜索樹(shù)
- 恢復(fù)二叉搜索樹(shù)
二叉搜索樹(shù)中的兩個(gè)節(jié)點(diǎn)被錯(cuò)誤地交換。
請(qǐng)?jiān)诓桓淖兤浣Y(jié)構(gòu)的情況下，恢復(fù)這棵樹(shù)。
示例 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
進(jìn)階:
- 使用 O(n) 空間復(fù)雜度的解法很容易實(shí)現(xiàn)。
- 你能想出一個(gè)只使用常數(shù)空間的解決方案嗎？
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);
// 找到交換的兩個(gè)節(jié)點(diǎn)
if(first == null && pre.val > root.val) {
first = pre;
}
if(first != null && pre.val > root.val) {
second = root;
}
pre = root;
robot(root.right);
}
修剪二叉搜索樹(shù)
- 修剪二叉搜索樹(shù)
給定一個(gè)二叉搜索樹(shù)，同時(shí)給定最小邊界L 和最大邊界 R。通過(guò)修剪二叉搜索樹(shù)，使得所有節(jié)點(diǎn)的值在[L, R]中 (R>=L) 。你可能需要改變樹(shù)的根節(jié)點(diǎn)，所以結(jié)果應(yīng)當(dāng)返回修剪好的二叉搜索樹(shù)的新的根節(jié)點(diǎn)。
示例 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;
}
將有序數(shù)組轉(zhuǎn)換為二叉搜索樹(shù)
- 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹(shù)
將一個(gè)按照升序排列的有序數(shù)組，轉(zhuǎn)換為一棵高度平衡二叉搜索樹(shù)。
本題中，一個(gè)高度平衡二叉樹(shù)是指一個(gè)二叉樹(shù)每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò) 1。
示例:
給定有序數(shù)組: [-10,-3,0,5,9],
一個(gè)可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面這個(gè)高度平衡二叉搜索樹(shù)：
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;
}
二叉搜索樹(shù)迭代器
- 二叉搜索樹(shù)迭代器
實(shí)現(xiàn)一個(gè)二叉搜索樹(shù)迭代器。你將使用二叉搜索樹(shù)的根節(jié)點(diǎn)初始化迭代器。
調(diào)用 next() 將返回二叉搜索樹(shù)中的下一個(gè)最小的數(shù)。
示例：
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() 操作的時(shí)間復(fù)雜度是 O(1)，并使用 O(h) 內(nèi)存，其中 h 是樹(shù)的高度。
- 你可以假設(shè) next() 調(diào)用總是有效的，也就是說(shuō)，當(dāng)調(diào)用 next() 時(shí)，BST 中至少存在一個(gè)下一個(gè)最小的數(shù)。
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;
// 訪問(wèn)當(dāng)前元素（中），把右兒子入棧（右）
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();
*/
二叉搜索樹(shù)中第K小的元素
- 二叉搜索樹(shù)中第K小的元素
給定一個(gè)二叉搜索樹(shù)，編寫(xiě)一個(gè)函數(shù) kthSmallest 來(lái)查找其中第 k 個(gè)最小的元素。
說(shuō)明：
你可以假設(shè) k 總是有效的，1 ≤ k ≤ 二叉搜索樹(shù)元素個(gè)數(shù)。
示例 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
進(jìn)階：
如果二叉搜索樹(shù)經(jīng)常被修改（插入/刪除操作）并且你需要頻繁地查找第 k 小的值，你將如何優(yōu)化 kthSmallest 函數(shù)？
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);
}
二叉搜索樹(shù)的最近公共祖先
- 二叉搜索樹(shù)的最近公共祖先
給定一個(gè)二叉搜索樹(shù), 找到該樹(shù)中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先。
百度百科中最近公共祖先的定義為：“對(duì)于有根樹(shù) T 的兩個(gè)結(jié)點(diǎn) p、q，最近公共祖先表示為一個(gè)結(jié)點(diǎn) x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個(gè)節(jié)點(diǎn)也可以是它自己的祖先）?！?/p>
例如，給定如下二叉搜索樹(shù): root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
輸出: 6
解釋: 節(jié)點(diǎn) 2 和節(jié)點(diǎn) 8 的最近公共祖先是 6。
示例 2:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
輸出: 2
解釋: 節(jié)點(diǎn) 2 和節(jié)點(diǎn) 4 的最近公共祖先是 2, 因?yàn)楦鶕?jù)定義最近公共祖先節(jié)點(diǎn)可以為節(jié)點(diǎn)本身。
說(shuō)明:
- 所有節(jié)點(diǎn)的值都是唯一的。
- p、q 為不同節(jié)點(diǎn)且均存在于給定的二叉搜索樹(shù)中。
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;
}
刪除二叉搜索樹(shù)中的節(jié)點(diǎn)
- 刪除二叉搜索樹(shù)中的節(jié)點(diǎn)
給定一個(gè)二叉搜索樹(shù)的根節(jié)點(diǎn) root 和一個(gè)值 key，刪除二叉搜索樹(shù)中的 key 對(duì)應(yīng)的節(jié)點(diǎn)，并保證二叉搜索樹(shù)的性質(zhì)不變。返回二叉搜索樹(shù)（有可能被更新）的根節(jié)點(diǎn)的引用。
一般來(lái)說(shuō)，刪除節(jié)點(diǎn)可分為兩個(gè)步驟：
- 首先找到需要?jiǎng)h除的節(jié)點(diǎn)；
- 如果找到了，刪除它。
說(shuō)明： 要求算法時(shí)間復(fù)雜度為 O(h)，h 為樹(shù)的高度。
示例:
root = [5,3,6,2,4,null,7]
key = 3
5
/ \
3 6
/ \ \
2 4 7
給定需要?jiǎng)h除的節(jié)點(diǎn)值是 3，所以我們首先找到 3 這個(gè)節(jié)點(diǎn)，然后刪除它。
一個(gè)正確的答案是 [5,4,6,2,null,null,7], 如下圖所示。
5
/ \
4 6
/ \
2 7
另一個(gè)正確答案是 [5,2,6,null,4,null,7]。
5
/ \
2 6
\ \
4 7
// todo 題目復(fù)雜，面試時(shí)不會(huì)?？?，考慮忽略此題目
二叉搜索樹(shù)中的搜索
- 二叉搜索樹(shù)中的搜索
給定二叉搜索樹(shù)（BST）的根節(jié)點(diǎn)和一個(gè)值。 你需要在BST中找到節(jié)點(diǎn)值等于給定值的節(jié)點(diǎn)。 返回以該節(jié)點(diǎn)為根的子樹(shù)。 如果節(jié)點(diǎn)不存在，則返回 NULL。
例如，
給定二叉搜索樹(shù):
4
/ \
2 7
/ \
1 3
和值: 2
你應(yīng)該返回如下子樹(shù):
2
/ \
1 3
在上述示例中，如果要找的值是 5，但因?yàn)闆](méi)有節(jié)點(diǎn)值為 5，我們應(yīng)該返回 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;
}
二叉搜索樹(shù)中的插入操作
給定二叉搜索樹(shù)（BST）的根節(jié)點(diǎn)和要插入樹(shù)中的值，將值插入二叉搜索樹(shù)。 返回插入后二叉搜索樹(shù)的根節(jié)點(diǎn)。 保證原始二叉搜索樹(shù)中不存在新值。
注意，可能存在多種有效的插入方式，只要樹(shù)在插入后仍保持為二叉搜索樹(shù)即可。 你可以返回任意有效的結(jié)果。
例如,
給定二叉搜索樹(shù):
4
/ \
2 7
/ \
1 3
和 插入的值: 5
你可以返回這個(gè)二叉搜索樹(shù):
4
/ \
2 7
/ \ /
1 3 5
或者這個(gè)樹(shù)也是有效的:
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;
}
深搜、廣搜
相同的樹(shù)
給定兩個(gè)二叉樹(shù)，編寫(xiě)一個(gè)函數(shù)來(lái)檢驗(yàn)它們是否相同。
如果兩個(gè)樹(shù)在結(jié)構(gòu)上相同，并且節(jié)點(diǎn)具有相同的值，則認(rèn)為它們是相同的。
示例 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);
}
對(duì)稱二叉樹(shù)
給定一個(gè)二叉樹(shù)，檢查它是否是鏡像對(duì)稱的。
例如，二叉樹(shù) [1,2,2,3,4,4,3] 是對(duì)稱的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面這個(gè) [1,2,2,null,3,null,3] 則不是鏡像對(duì)稱的:
1
/ \
2 2
\ \
3 3
說(shuō)明:
如果你可以運(yùn)用遞歸和迭代兩種方法解決這個(gè)問(wèn)題，會(huì)很加分。
遞歸
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;
}
翻轉(zhuǎn)二叉樹(shù)
- 翻轉(zhuǎn)二叉樹(shù)
示例：
輸入：
4
/ \
2 7
/ \ / \
1 3 6 9
輸出：
4
/ \
7 2
/ \ / \
9 6 3 1
備注:
這個(gè)問(wèn)題是受到 Max Howell 的 原問(wèn)題 啟發(fā)的 ：
谷歌：我們90％的工程師使用您編寫(xiě)的軟件(Homebrew)，但是您卻無(wú)法在面試時(shí)在白板上寫(xiě)出翻轉(zhuǎn)二叉樹(shù)這道題，這太糟糕了。
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;
}
二叉樹(shù)的最大深度
- 二叉樹(shù)的最大深度
給定一個(gè)二叉樹(shù)，找出其最大深度。
二叉樹(shù)的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)。
說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例：
給定二叉樹(shù) [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);
}
二叉樹(shù)的最小深度
- 二叉樹(shù)的最小深度
給定一個(gè)二叉樹(shù)，找出其最小深度。
最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。
說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例:
給定二叉樹(shù) [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;
}
平衡二叉樹(shù)
- 平衡二叉樹(shù)
給定一個(gè)二叉樹(shù)，判斷它是否是高度平衡的二叉樹(shù)。
本題中，一棵高度平衡二叉樹(shù)定義為：
一個(gè)二叉樹(shù)每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1。
示例 1:
給定二叉樹(shù) [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
給定二叉樹(shù) [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;
}
完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)
給出一個(gè)完全二叉樹(shù)，求出該樹(shù)的節(jié)點(diǎn)個(gè)數(shù)。
說(shuō)明：
完全二叉樹(shù)的定義如下：在完全二叉樹(shù)中，除了最底層節(jié)點(diǎn)可能沒(méi)填滿外，其余每層節(jié)點(diǎn)數(shù)都達(dá)到最大值，并且最下面一層的節(jié)點(diǎn)都集中在該層最左邊的若干位置。若最底層為第 h 層，則該層包含 1~ 2^h 個(gè)節(jié)點(diǎn)。
示例:
輸入:
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;
}
二叉樹(shù)最大寬度
- 二叉樹(shù)最大寬度
給定一個(gè)二叉樹(shù)，編寫(xiě)一個(gè)函數(shù)來(lái)獲取這個(gè)樹(shù)的最大寬度。樹(shù)的寬度是所有層中的最大寬度。這個(gè)二叉樹(shù)與 滿二叉樹(shù)（full binary tree） 結(jié)構(gòu)相同，但一些節(jié)點(diǎn)為空。
每一層的寬度被定義為兩個(gè)端點(diǎn)（該層最左和最右的非空節(jié)點(diǎn)，兩端點(diǎn)間的null節(jié)點(diǎn)也計(jì)入長(zhǎng)度）之間的長(zhǎng)度。
示例 1:
輸入:
1
/ \
3 2
/ \ \
5 3 9
輸出: 4
解釋: 最大值出現(xiàn)在樹(shù)的第 3 層，寬度為 4 (5,3,null,9)。
示例 2:
輸入:
1
/
3
/ \
5 3
輸出: 2
解釋: 最大值出現(xiàn)在樹(shù)的第 3 層，寬度為 2 (5,3)。
示例 3:
輸入:
1
/ \
3 2
/
5
輸出: 2
解釋: 最大值出現(xiàn)在樹(shù)的第 2 層，寬度為 2 (3,2)。
示例 4:
輸入:
1
/ \
3 2
/ \
5 9
/ \
6 7
輸出: 8
解釋: 最大值出現(xiàn)在樹(shù)的第 4 層，寬度為 8 (6,null,null,null,null,null,null,7)。
注意: 答案在32位有符號(hào)整數(shù)的表示范圍內(nèi)。
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);
}
二叉樹(shù)的直徑
- 二叉樹(shù)的直徑
給定一棵二叉樹(shù)，你需要計(jì)算它的直徑長(zhǎng)度。一棵二叉樹(shù)的直徑長(zhǎng)度是任意兩個(gè)結(jié)點(diǎn)路徑長(zhǎng)度中的最大值。這條路徑可能穿過(guò)根結(jié)點(diǎn)。
示例 :
給定二叉樹(shù)
1
/ \
2 3
/ \
4 5
返回 3, 它的長(zhǎng)度是路徑 [4,2,1,3] 或者 [5,2,1,3]。
注意：兩結(jié)點(diǎn)之間的路徑長(zhǎng)度是以它們之間邊的數(shù)目表示。
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);
// 維護(hù)直徑最大值
ans[0] = Math.max(left + right, ans[0]);
// 返回當(dāng)前節(jié)點(diǎn)的最大直徑
return Math.max(left, right) + 1;
}
二叉樹(shù)的坡度
- 二叉樹(shù)的坡度
給定一個(gè)二叉樹(shù)，計(jì)算整個(gè)樹(shù)的坡度。
一個(gè)樹(shù)的節(jié)點(diǎn)的坡度定義即為，該節(jié)點(diǎn)左子樹(shù)的結(jié)點(diǎn)之和和右子樹(shù)結(jié)點(diǎn)之和的差的絕對(duì)值?？战Y(jié)點(diǎn)的的坡度是0。
整個(gè)樹(shù)的坡度就是其所有節(jié)點(diǎn)的坡度之和。
示例:
輸入:
1
/ \
2 3
輸出: 1
解釋:
結(jié)點(diǎn)的坡度 2 : 0
結(jié)點(diǎn)的坡度 3 : 0
結(jié)點(diǎn)的坡度 1 : |2-3| = 1
樹(shù)的坡度 : 0 + 0 + 1 = 1
注意:
- 任何子樹(shù)的結(jié)點(diǎn)的和不會(huì)超過(guò)32位整數(shù)的范圍。
- 坡度的值不會(huì)超過(guò)32位整數(shù)的范圍。
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;
}
二叉樹(shù)的所有路徑
- 二叉樹(shù)的所有路徑
給定一個(gè)二叉樹(shù)，返回所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑。
說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例:
輸入:
1
/ \
2 3
\
5
輸出: ["1->2->5", "1->3"]
解釋: 所有根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑為: 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 + "->");
}
二叉樹(shù)的最近公共祖先
- 二叉樹(shù)的最近公共祖先
給定一個(gè)二叉樹(shù), 找到該樹(shù)中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先。
百度百科中最近公共祖先的定義為：“對(duì)于有根樹(shù) T 的兩個(gè)結(jié)點(diǎn) p、q，最近公共祖先表示為一個(gè)結(jié)點(diǎn) x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個(gè)節(jié)點(diǎn)也可以是它自己的祖先）?！?/p>
例如，給定如下二叉樹(shù): root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出: 3
解釋: 節(jié)點(diǎn) 5 和節(jié)點(diǎn) 1 的最近公共祖先是節(jié)點(diǎn) 3。
示例 2:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出: 5
解釋: 節(jié)點(diǎn) 5 和節(jié)點(diǎn) 4 的最近公共祖先是節(jié)點(diǎn) 5。因?yàn)楦鶕?jù)定義最近公共祖先節(jié)點(diǎn)可以為節(jié)點(diǎn)本身。
說(shuō)明:
- 所有節(jié)點(diǎn)的值都是唯一的。
- p、q 為不同節(jié)點(diǎn)且均存在于給定的二叉樹(shù)中。
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;
}
最深葉節(jié)點(diǎn)的最近公共祖先
- 最深葉節(jié)點(diǎn)的最近公共祖先
給你一個(gè)有根節(jié)點(diǎn)的二叉樹(shù)，找到它最深的葉節(jié)點(diǎn)的最近公共祖先。
回想一下：
- 葉節(jié)點(diǎn) 是二叉樹(shù)中沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)
- 樹(shù)的根節(jié)點(diǎn)的 深度 為 0，如果某一節(jié)點(diǎn)的深度為 d，那它的子節(jié)點(diǎn)的深度就是 d+1
- 如果我們假定 A 是一組節(jié)點(diǎn) S 的 最近公共祖先 中的每個(gè)節(jié)點(diǎn)都在以 A 為根節(jié)點(diǎn)的子樹(shù)中，且 A 的深度達(dá)到此條件下可能的最大值。
示例 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]
提示：
- 給你的樹(shù)中將有 1 到 1000 個(gè)節(jié)點(diǎn)。
- 樹(shù)中每個(gè)節(jié)點(diǎn)的值都在 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;
}
路徑和
左葉子之和
- 左葉子之和
計(jì)算給定二叉樹(shù)的所有左葉子之和。
示例：
3
/ \
9 20
/ \
15 7
在這個(gè)二叉樹(shù)中，有兩個(gè)左葉子，分別是 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);
}
路徑總和
- 路徑總和
給定一個(gè)二叉樹(shù)和一個(gè)目標(biāo)和，判斷該樹(shù)中是否存在根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑，這條路徑上所有節(jié)點(diǎn)值相加等于目標(biāo)和。
說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例:
給定如下二叉樹(shù)，以及目標(biāo)和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因?yàn)榇嬖谀繕?biāo)和為 22 的根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑 5->4->11->2。
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
// 葉子節(jié)點(diǎn) && 和為 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
給定一個(gè)二叉樹(shù)和一個(gè)目標(biāo)和，找到所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)路徑總和等于給定目標(biāo)和的路徑。
說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例:
給定如下二叉樹(shù)，以及目標(biāo)和 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
給定一個(gè)二叉樹(shù)，它的每個(gè)結(jié)點(diǎn)都存放著一個(gè)整數(shù)值。
找出路徑和等于給定數(shù)值的路徑總數(shù)。
路徑不需要從根節(jié)點(diǎn)開(kāi)始，也不需要在葉子節(jié)點(diǎn)結(jié)束，但是路徑方向必須是向下的（只能從父節(jié)點(diǎn)到子節(jié)點(diǎn)）。
二叉樹(shù)不超過(guò)1000個(gè)節(jié)點(diǎn)，且節(jié)點(diǎn)數(shù)值范圍是 [-1000000,1000000] 的整數(shù)。
示例：
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;
}
二叉樹(shù)中的最大路徑和
- 二叉樹(shù)中的最大路徑和
給定一個(gè)非空二叉樹(shù)，返回其最大路徑和。
本題中，路徑被定義為一條從樹(shù)中任意節(jié)點(diǎn)出發(fā)，達(dá)到任意節(jié)點(diǎn)的序列。該路徑至少包含一個(gè)節(jié)點(diǎn)，且不一定經(jīng)過(guò)根節(jié)點(diǎn)。
示例 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;
}
求根到葉子節(jié)點(diǎn)數(shù)字之和
- 求根到葉子節(jié)點(diǎn)數(shù)字之和
給定一個(gè)二叉樹(shù)，它的每個(gè)結(jié)點(diǎn)都存放一個(gè) 0-9 的數(shù)字，每條從根到葉子節(jié)點(diǎn)的路徑都代表一個(gè)數(shù)字。
例如，從根到葉子節(jié)點(diǎn)路徑 1->2->3 代表數(shù)字 123。
計(jì)算從根到葉子節(jié)點(diǎn)生成的所有數(shù)字之和。
說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例 1:
輸入: [1,2,3]
1
/ \
2 3
輸出: 25
解釋:
從根到葉子節(jié)點(diǎn)路徑 1->2 代表數(shù)字 12.
從根到葉子節(jié)點(diǎn)路徑 1->3 代表數(shù)字 13.
因此，數(shù)字總和 = 12 + 13 = 25.
示例 2:
輸入: [4,9,0,5,1]
4
/ \
9 0
/ \
5 1
輸出: 1026
解釋:
從根到葉子節(jié)點(diǎn)路徑 4->9->5 代表數(shù)字 495.
從根到葉子節(jié)點(diǎn)路徑 4->9->1 代表數(shù)字 491.
從根到葉子節(jié)點(diǎn)路徑 4->0 代表數(shù)字 40.
因此，數(shù)字總和 = 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);
}
序列化二叉樹(shù)、構(gòu)造二叉樹(shù)
從前序與中序遍歷序列構(gòu)造二叉樹(shù)
- 從前序與中序遍歷序列構(gòu)造二叉樹(shù)
根據(jù)一棵樹(shù)的前序遍歷與中序遍歷構(gòu)造二叉樹(shù)。
注意:
你可以假設(shè)樹(shù)中沒(méi)有重復(fù)的元素。
例如，給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹(shù)：
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;
}
從中序與后序遍歷序列構(gòu)造二叉樹(shù)
- 從中序與后序遍歷序列構(gòu)造二叉樹(shù)
根據(jù)一棵樹(shù)的中序遍歷與后序遍歷構(gòu)造二叉樹(shù)。
注意:
你可以假設(shè)樹(shù)中沒(méi)有重復(fù)的元素。
例如，給出
中序遍歷 inorder = [9,3,15,20,7]
后序遍歷 postorder = [9,15,7,20,3]
返回如下的二叉樹(shù)：
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;
}
先序遍歷構(gòu)造二叉樹(shù)
- 先序遍歷構(gòu)造二叉樹(shù)
返回與給定先序遍歷 preorder 相匹配的二叉搜索樹(shù)（binary search tree）的根結(jié)點(diǎn)。
(回想一下，二叉搜索樹(shù)是二叉樹(shù)的一種，其每個(gè)節(jié)點(diǎn)都滿足以下規(guī)則，對(duì)于 node.left 的任何后代，值總 < node.val，而 node.right 的任何后代，值總 > node.val。此外，先序遍歷首先顯示節(jié)點(diǎn)的值，然后遍歷 node.left，接著遍歷 node.right。）
示例：
輸入：[8,5,1,7,10,12]
輸出：[8,5,10,1,7,null,12]
@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;
}
序列化和反序列化二叉搜索樹(shù)
- 序列化和反序列化二叉搜索樹(shù)
序列化是將數(shù)據(jù)結(jié)構(gòu)或?qū)ο筠D(zhuǎn)換為一系列位的過(guò)程，以便它可以存儲(chǔ)在文件或內(nèi)存緩沖區(qū)中，或通過(guò)網(wǎng)絡(luò)連接鏈路傳輸，以便稍后在同一個(gè)或另一個(gè)計(jì)算機(jī)環(huán)境中重建。
設(shè)計(jì)一個(gè)算法來(lái)序列化和反序列化二叉搜索樹(shù)。 對(duì)序列化/反序列化算法的工作方式?jīng)]有限制。 您只需確保二叉搜索樹(shù)可以序列化為字符串，并且可以將該字符串反序列化為最初的二叉搜索樹(shù)。
編碼的字符串應(yīng)盡可能緊湊。
注意：不要使用類成員/全局/靜態(tài)變量來(lái)存儲(chǔ)狀態(tài)。 你的序列化和反序列化算法應(yīng)該是無(wú)狀態(tài)的。
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]));
// 找到對(duì)應(yīng)的 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));
二叉樹(shù)的序列化與反序列化
- 二叉樹(shù)的序列化與反序列化
序列化是將一個(gè)數(shù)據(jù)結(jié)構(gòu)或者對(duì)象轉(zhuǎn)換為連續(xù)的比特位的操作，進(jìn)而可以將轉(zhuǎn)換后的數(shù)據(jù)存儲(chǔ)在一個(gè)文件或者內(nèi)存中，同時(shí)也可以通過(guò)網(wǎng)絡(luò)傳輸?shù)搅硪粋€(gè)計(jì)算機(jī)環(huán)境，采取相反方式重構(gòu)得到原數(shù)據(jù)。
請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法來(lái)實(shí)現(xiàn)二叉樹(shù)的序列化與反序列化。這里不限定你的序列 / 反序列化算法執(zhí)行邏輯，你只需要保證一個(gè)二叉樹(shù)可以被序列化為一個(gè)字符串并且將這個(gè)字符串反序列化為原始的樹(shù)結(jié)構(gòu)。
示例:
你可以將以下二叉樹(shù)：
1
/ \
2 3
/ \
4 5
序列化為 "[1,2,3,null,null,4,5]"
提示: 這與 LeetCode 目前使用的方式一致，詳情請(qǐng)參閱 LeetCode 序列化二叉樹(shù)的格式。你并非必須采取這種方式，你也可以采用其他的方法解決這個(gè)問(wèn)題。
說(shuō)明: 不要使用類的成員 / 全局 / 靜態(tài)變量來(lái)存儲(chǔ)狀態(tài)，你的序列化和反序列化算法應(yīng)該是無(wú)狀態(tài)的。
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];
}
