二叉树练习

一些经典的二叉树练习题,帮助理解掌握二叉树的各种遍历方法和递归地解决问题的思路。

二叉树节点定义

  • java
1
2
3
4
5
6
7
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
  • python
1
2
3
4
5
6
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None

利用中序和后序遍历序列重建二叉树

给定一棵树的中序和后序遍历结果,构造二叉树。

注意:您可以假定树中不存在重复项。

例如,给定

1
2
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

返回以下二叉树:

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

java 参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder == null || postorder == null || inorder.length != postorder.length) {
return null;
}
HashMap<Integer, Integer> map = new HashMap<>(inorder.length);
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return build(0, postorder, 0, postorder.length - 1, map);
}

private TreeNode build(int si, int[] post, int sp, int ep, HashMap<Integer, Integer> map) {
if (sp > ep) {
return null;
}
TreeNode root = new TreeNode(post[ep]);
int idx = map.get(root.val);
int leftLen = idx - si;
root.left = build(si, post, sp, sp + leftLen - 1, map);
root.right = build(idx + 1, post, sp + leftLen, ep - 1, map);
return root;
}
}

python 参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from typing import List


class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
if not inorder or not postorder or len(inorder) != len(postorder):
return

indices = {v: i for i, v in enumerate(inorder)}
return self.build(0, postorder, 0, len(postorder) - 1, indices)

def build(self, si: int, post: List[int], sp: int, ep: int,
indices: dict) -> TreeNode:
if sp > ep:
return

root = TreeNode(post[ep])
idx = indices[root.val]
llen = idx - si

root.left = self.build(si, post, sp, sp + llen - 1, indices)
root.right = self.build(idx + 1, post, sp + llen, ep - 1, indices)

return root

利用前序和中序遍历序列重建二叉树

给定一棵树的前序和中序遍历结果,构造二叉树。

注意:您可以假定树中不存在重复项。

例如,给定

1
2
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

返回以下二叉树:

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

java 参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null || preorder.length != inorder.length) {
return null;
}
HashMap<Integer, Integer> map = new HashMap<>(inorder.length);
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return build(0, preorder, 0, preorder.length - 1, map);
}

private TreeNode build(int si, int[] pre, int sp, int ep,
HashMap<Integer, Integer> map) {
if (sp > ep) {
return null;
}
TreeNode root = new TreeNode(pre[sp]);
int idx = map.get(root.val);
int leftLen = idx - si;
root.left = build(si, pre, sp + 1, sp + leftLen, map);
root.right = build(idx + 1, pre, sp + leftLen + 1, ep, map);
return root;
}
}

python 参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from typing import List


class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder or not inorder or len(preorder) != len(inorder):
return

indices = {v: i for i, v in enumerate(inorder)}
return self.build(preorder, 0, len(preorder) - 1, 0, indices)

def build(self, pre: List[int], sp: int, ep: int, si: int,
indices: dict) -> TreeNode:
if sp > ep:
return

root = TreeNode(pre[sp])
idx = indices[root.val]
llen = idx - si

root.left = self.build(pre, sp + 1, sp + llen, si, indices)
root.right = self.build(pre, sp + llen + 1, ep, idx + 1, indices)

return root

填充每个节点的下一个右侧节点指针

您会得到一棵完美的二叉树,其中所有叶子都在同一水平上,每个父级都有两个孩子。二叉树定义如下:

1
2
3
4
5
6
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

填充每个 next 指针以指向其下一个右节点。如果没有下一个右节点,则 next 指针应设置为 NULL。

最初,所有 next 指针都设置为 NULL。

Follow up:

  • 您只能使用常量的额外空间。
  • 递归方法很好,您可以假定隐式堆栈空间不算作此问题的额外空间。

Example 1:

116-sample

1
2
3
4
5
Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: 给定上面完美的二叉树(图A),您的函数应该填充每个下一个指针,
以指向其下一个右节点,如图B所示。序列化的输出按层次顺序排列,与下一个指针相连,
并带有 '#' 表示每个层次的结束。

限制条件:

  • 给定树中的节点数少于4096。
  • -1000 <= node.val <= 1000

java 参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
* Definition for a Node.
* class Node {
* public int val;
* public Node left;
* public Node right;
* public Node next;
*
* public Node() {}
*
* public Node(int _val) {
* val = _val;
* }
*
* public Node(int _val, Node _left, Node _right, Node * _next) {
* val = _val;
* left = _left;
* right = _right;
* next = _next;
* }
* };
*/

class Solution {
public Node connect(Node root) {
Node levelStart = root;
while (levelStart != null) {
Node cur = levelStart;
while (cur != null) {
if (cur.left != null) {
cur.left.next = cur.right;
if (cur.next != null) {
cur.right.next = cur.next.left;
}
}
cur = cur.next;
}
levelStart = levelStart.left;
}
return root;
}
}

python 参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Definition for a Node.
# class Node:
# def __init__(self,
# val: int = 0,
# left: 'Node' = None,
# right: 'Node' = None,
# next: 'Node' = None):
# self.val = val
# self.left = left
# self.right = right
# self.next = next


class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return

cur = root
while cur.left:
head = cur.left

while cur:
cur.left.next = cur.right
if cur.next:
cur.right.next = cur.next.left
cur = cur.next

cur = head

return root

填充每个节点的下一个右侧节点指针II

给定一棵二叉树:

1
2
3
4
5
6
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

填充每个 next 指针以指向其下一个右节点。如果没有下一个右节点,则 next 指针应设置为 NULL。

最初,所有 next 指针都设置为 NULL。

Follow up:

  • 您只能使用常量的额外空间。
  • 递归方法很好,您可以假定隐式堆栈空间不算作此问题的额外空间。

Example 1:

117-sample

1
2
3
4
5
Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: 给定上面的二叉树(图A),您的函数应该填充每个下一个指针,
以指向其下一个右节点,如图B所示。序列化的输出按层次顺序排列,与下一个指针相连,
并用 '#' 表示 每个层次的结尾。

限制条件:

  • 给定树中的节点数少于6000。
  • -100 <= node.val <= 100

java 参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public Node connect(Node root) {
Node nextHeadDummy = new Node(0);
Node nextLevelCur = nextHeadDummy;
Node cur = root;
while (cur != null) {
while (cur != null) {
if (cur.left != null) {
nextLevelCur.next = cur.left;
nextLevelCur = nextLevelCur.next;
}
if (cur.right != null) {
nextLevelCur.next = cur.right;
nextLevelCur = nextLevelCur.next;
}
cur = cur.next;
}
cur = nextHeadDummy.next;
nextHeadDummy.next = null;
nextLevelCur = nextHeadDummy;
}
return root;
}
}

python 参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# Definition for a Node.
# class Node:
# def __init__(self,
# val: int = 0,
# left: 'Node' = None,
# right: 'Node' = None,
# next: 'Node' = None):
# self.val = val
# self.left = left
# self.right = right


class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return

cur = root
while cur:
head, pre = None, None

while cur:
if cur.left:
if pre:
pre.next = cur.left
else:
head = cur.left
pre = cur.left

if cur.right:
if pre:
pre.next = cur.right
else:
head = cur.right
pre = cur.right

cur = cur.next

cur = head

return root

二叉树的最低共同祖先

给定二叉树,在树中找到两个给定节点的最低公共祖先(LCA)。

根据Wikipedia上LCA的定义:“最低的共同祖先被定义为两个节点p和q之间的关系,这是T中同时具有p和q作为后代的最低节点(我们允许一个节点成为其自身的后代)。 ”

给定以下二叉树:root = [3,5,1,6,2,0,8,null,null,7,4]

binarytree

Example 1:

1
2
3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

1
2
3
4
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be
a descendant of itself according to the LCA definition.

注意:

  • 所有节点的值都是唯一的。
  • p和q不同,并且两个值都将存在于二叉树中。

java 参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
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 ? left : right;
}
}

python 参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def lowestCommonAncestor(self, root, p, q):
if not root or root == p or root == q:
return root

left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)

if left and right:
return root

return left or right

二叉树的序列化与反序列化

序列化是将数据结构或对象转换为位序列的过程,以便可以将其存储在文件或内存缓冲区中,或者通过网络连接进行传输,以便稍后在相同或另一个计算机环境中进行重构。

设计一种用于对二叉树进行序列化和反序列化的算法。序列化/反序列化算法的工作方式没有任何限制。您只需要确保可以将二叉树序列化为字符串,并且可以将该字符串反序列化为原始树结构。

Example:

1
2
3
4
5
6
7
8
9
You may serialize the following tree:

1
/ \
2 3
/ \
4 5

as "[1,2,3,null,null,4,5]"

说明:上面的格式与 LeetCode 序列化二叉树的方式相同。您不一定需要遵循这种格式,因此请发挥创造力并自己提出不同的方法。

注意:不要使用类成员/全局/静态变量来存储状态。您的序列化和反序列化算法应该是无状态的。

java 参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Codec {
private static final String DELIMITER = ",";
private static final String PADDING = "$";

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serialize(root, sb);
return sb.toString();
}

private void serialize(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append(PADDING).append(DELIMITER);
return;
}
sb.append(root.val).append(DELIMITER);
serialize(root.left, sb);
serialize(root.right, sb);
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
LinkedList<String> queue = new LinkedList<>(Arrays.asList(data.split(DELIMITER)));
return deserialize(queue);
}

private TreeNode deserialize(LinkedList<String> queue) {
String val = queue.poll();
if (PADDING.equals(val)) {
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(val));
root.left = deserialize(queue);
root.right = deserialize(queue);
return root;
}
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

python 参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
from typing import List


class Codec:
def serialize(self, root: TreeNode) -> str:
"""Encodes a tree to a single string.

Args:
root (TreeNode): the root of tree

Returns:
str: a serial str of binary tree
"""
res = []
self._serial(root, res)
return ','.join(res)

def _serial(self, root: TreeNode, res: List[str]) -> None:
if not root:
res.append('#')
return

res.append(str(root.val))
self._serial(root.left, res)
self._serial(root.right, res)

def deserialize(self, data: str) -> TreeNode:
"""Decodes your encoded data to tree.

Args:
data (str): a serial str of binary tree

Returns:
TreeNode: the root of tree
"""
data = data.split(',')
data.reverse()
return self._deserial(data)

def _deserial(self, data: List[str]) -> TreeNode:
val = data.pop()
if val == '#':
return

root = TreeNode(int(val))
root.left = self._deserial(data)
root.right = self._deserial(data)

return root


# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

References

https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/942/

https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/943/

https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/994/

https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/1016/

https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/932/

https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/995/