二叉树
二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
输入：root = [1,null,2,3]
输出：[1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
from typing import List, Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def inorderTraversal_recursive(self, root: Optional[TreeNode]) -> List[int]:
"""
方法一：递归（最简单直观）
思路：
- 中序遍历顺序：左子树 -> 根节点 -> 右子树
- 递归处理左子树，访问根节点，递归处理右子树
- 时间 O(n)，空间 O(h)，h 为树的高度（递归栈深度）
"""
result = []
def inorder(node):
if not node:
return
inorder(node.left) # 遍历左子树
result.append(node.val) # 访问根节点
inorder(node.right) # 遍历右子树
inorder(root)
return result
def inorderTraversal_iterative(self, root: Optional[TreeNode]) -> List[int]:
"""
方法二：迭代（模拟递归栈）
思路：
- 递归本质上是在维护一个调用栈
- 迭代需要手动用栈来模拟
- 1. 先把左子树全部压栈
- 2. 弹出栈顶访问，然后处理右子树
- 时间 O(n)，空间 O(h)
"""
result = []
stack = []
current = root
while current or stack:
# 1. 先把当前节点的左子树全部压栈
while current:
stack.append(current)
current = current.left
# 2. 弹出栈顶，访问节点
current = stack.pop()
result.append(current.val)
# 3. 处理右子树
current = current.right
return result
# 测试用例
def build_tree(values):
"""根据层序数组构建二叉树"""
if not values:
return None
root = TreeNode(values[0])
queue = [root]
i = 1
while queue and i < len(values):
node = queue.pop(0)
# 左子节点
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
# 右子节点
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
# 示例1: [1,null,2,3] -> [1,3,2]
root = build_tree([1, None, 2, None, None, 3, None])
assert Solution().inorderTraversal_recursive(root) == [1, 3, 2]
assert Solution().inorderTraversal_iterative(root) == [1, 3, 2]
# 示例2: [] -> []
root = build_tree([])
assert Solution().inorderTraversal_recursive(root) == []
assert Solution().inorderTraversal_iterative(root) == []
# 示例3: [1] -> [1]
root = build_tree([1])
assert Solution().inorderTraversal_recursive(root) == [1]
assert Solution().inorderTraversal_iterative(root) == [1]
# 更多测试
root = build_tree([4, 2, 6, 1, 3, 5, 7]) # 平衡二叉树
assert Solution().inorderTraversal_recursive(root) == [1, 2, 3, 4, 5, 6, 7]
assert Solution().inorderTraversal_iterative(root) == [1, 2, 3, 4, 5, 6, 7]
# 手动推导（迭代法）树 [1,null,2,3]：
# 1
# \
# 2
# /
# 3
#
# 初始: current=1, stack=[], result=[]
#
# 第1次外层循环:
# current=1 != None, stack=[1], current=1.left=None
# current=None, 退出内层循环
# current=stack.pop()=1, result=[1]
# current=1.right=2
#
# 第2次外层循环:
# current=2 != None, stack=[2], current=2.left=3
# current=3 != None, stack=[2,3], current=3.left=None
# current=None, 退出内层循环
# current=stack.pop()=3, result=[1,3]
# current=3.right=None
#
# 第3次外层循环:
# current=None, stack=[2]
# current=stack.pop()=2, result=[1,3,2]
# current=2.right=None
#
# 第4次外层循环:
# current=None, stack=[]
# 退出循环
#
# 结果: [1, 3, 2]
|
二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
输入：root = [3,9,20,null,null,15,7]
输出：3
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def maxDepth_recursive(self, root: Optional[TreeNode]) -> int:
"""
方法一：递归（深度优先搜索）
思路：
- 最大深度 = 1 + max(左子树深度, 右子树深度)
- 递归到叶子节点，返回 0
- 时间 O(n)，空间 O(h)，h 为树的高度（递归栈深度）
"""
if not root:
return 0
return 1 + max(self.maxDepth_recursive(root.left), self.maxDepth_recursive(root.right))
def maxDepth_iterative(self, root: Optional[TreeNode]) -> int:
"""
方法二：层序遍历（广度优先搜索）
思路：
- 使用队列按层遍历
- 遍历完一层，深度 +1
- 时间 O(n)，空间 O(w)，w 为最大宽度
"""
from collections import deque
if not root:
return 0
depth = 0
queue = deque([root])
while queue:
depth += 1
level_size = len(queue)
# 处理当前层的所有节点
for _ in range(level_size):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return depth
# 测试用例
def build_tree(values):
"""根据层序数组构建二叉树"""
if not values:
return None
root = TreeNode(values[0])
queue = [root]
i = 1
while queue and i < len(values):
node = queue.pop(0)
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
# 示例1: [3,9,20,null,null,15,7] -> 3
root = build_tree([3, 9, 20, None, None, 15, 7])
assert Solution().maxDepth_recursive(root) == 3
assert Solution().maxDepth_iterative(root) == 3
# 示例2: [1,null,2] -> 2
root = build_tree([1, None, 2])
assert Solution().maxDepth_recursive(root) == 2
assert Solution().maxDepth_iterative(root) == 2
# 更多测试
root = build_tree([])
assert Solution().maxDepth_recursive(root) == 0
assert Solution().maxDepth_iterative(root) == 0
root = build_tree([1])
assert Solution().maxDepth_recursive(root) == 1
assert Solution().maxDepth_iterative(root) == 1
root = build_tree([1, 2, 3, 4, 4, 4, 3]) # 完全二叉树
assert Solution().maxDepth_recursive(root) == 3
assert Solution().maxDepth_iterative(root) == 3
# 手动推导（递归法）树 [3,9,20,null,null,15,7]：
# 3
# / \
# 9 20
# / \
# 15 7
#
# maxDepth(3):
# = 1 + max(maxDepth(9), maxDepth(20))
#
# maxDepth(9):
# = 1 + max(maxDepth(None), maxDepth(None))
# = 1 + max(0, 0) = 1
#
# maxDepth(20):
# = 1 + max(maxDepth(15), maxDepth(7))
# = 1 + max(1, 1) = 2
#
# maxDepth(3) = 1 + max(1, 2) = 3
#
# 结果: 3
|
翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
|
from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def invertTree_recursive(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
"""
方法一：递归（深度优先搜索）
思路：
- 翻转当前节点的左右子树
- 递归翻转左子树和右子树
- 时间 O(n)，空间 O(h)
"""
if not root:
return root
# 交换左右子节点
root.left, root.right = root.right, root.left
# 递归翻转子树
self.invertTree_recursive(root.left)
self.invertTree_recursive(root.right)
return root
def invertTree_iterative(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
"""
方法二：层序遍历（广度优先搜索）
思路：
- 使用队列按层遍历
- 遍历时交换每个节点的左右子节点
- 时间 O(n)，空间 O(w)
"""
from collections import deque
if not root:
return root
queue = deque([root])
while queue:
node = queue.popleft()
# 交换左右子节点
node.left, node.right = node.right, node.left
# 将子节点加入队列
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return root
# 测试用例
def build_tree(values):
"""根据层序数组构建二叉树"""
if not values:
return None
root = TreeNode(values[0])
queue = [root]
i = 1
while queue and i < len(values):
node = queue.pop(0)
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
def tree_to_list(root):
"""层序遍历转列表"""
if not root:
return []
result = []
queue = [root]
while queue:
node = queue.pop(0)
if node:
result.append(node.val)
queue.append(node.left) if node.left else None
queue.append(node.right) if node.right else None
else:
result.append(None)
while result and result[-1] is None:
result.pop()
return result
# 示例1: [4,2,7,1,3,6,9] -> [4,7,2,9,6,3,1]
root = build_tree([4, 2, 7, 1, 3, 6, 9])
root = Solution().invertTree_recursive(root)
assert tree_to_list(root) == [4, 7, 2, 9, 6, 3, 1]
# 示例2: [2,1,3] -> [2,3,1]
root = build_tree([2, 1, 3])
root = Solution().invertTree_iterative(root)
assert tree_to_list(root) == [2, 3, 1]
# 示例3: [] -> []
root = build_tree([])
root = Solution().invertTree_recursive(root)
assert tree_to_list(root) == []
# 更多测试
root = build_tree([1])
root = Solution().invertTree_recursive(root)
assert tree_to_list(root) == [1]
root = build_tree([1, 2, 3, 4, 5])
root = Solution().invertTree_iterative(root)
assert tree_to_list(root) == [1, 3, 2, None, None, None, None, 5, 4]
# 手动推导（递归法）树 [4,2,7,1,3,6,9]：
# 翻转前: 翻转后:
# 4 4
# / \ / \
# 2 7 7 2
# / \ / \ / \ / \
# 1 3 6 9 9 6 3 1
#
# 递归过程（后序遍历）：
# invertTree(4):
# 交换 4 的左右子节点
# invertTree(2):
# 交换 2 的左右子节点
# invertTree(1): 无子节点，返回
# invertTree(3): 无子节点，返回
# 返回 2
# invertTree(7):
# 交换 7 的左右子节点
# invertTree(6): 无子节点，返回
# invertTree(9): 无子节点，返回
# 返回 7
# 返回 4
|
对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
输入：root = [1,2,2,3,4,4,3]
输出：true
进阶：你可以运用递归和迭代两种方法解决这个问题吗？
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
from typing import Optional
from collections import deque
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isSymmetric_recursive(self, root: Optional[TreeNode]) -> bool:
"""
方法一：递归
思路：
- 比较两棵子树是否互为镜像
- 两棵树对称的条件：
1. 两棵树的根节点值相同
2. 左树的左子树和右树的右子树对称
3. 左树的右子树和右树的左子树对称
- 时间 O(n)，空间 O(h)
"""
if not root:
return True
def isMirror(left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:
# 两棵树都为空，对称
if not left and not right:
return True
# 一棵树为空，另一棵不为空，不对称
if not left or not right:
return False
# 根节点值不同，不对称
if left.val != right.val:
return False
# 递归检查子树
return isMirror(left.left, right.right) and isMirror(left.right, right.left)
return isMirror(root.left, root.right)
def isSymmetric_iterative(self, root: Optional[TreeNode]) -> bool:
"""
方法二：迭代（使用队列）
思路：
- 将根节点的左右子节点成对加入队列
- 每次取出两个节点比较
- 如果是镜像关系，继续比较其子树
- 时间 O(n)，空间 O(w)
"""
if not root:
return True
queue = deque()
# 将左右子节点成对加入队列
if root.left and root.right:
queue.append((root.left, root.right))
elif root.left or root.right:
return False
while queue:
left, right = queue.popleft()
# 比较当前两个节点
if left.val != right.val:
return False
# 左树的左子树对应右树的右子树
if left.left and right.right:
queue.append((left.left, right.right))
elif left.left or right.right: # 一个有空一个没有，不对称
return False
# 左树的右子树对应右树的左子树
if left.right and right.left:
queue.append((left.right, right.left))
elif left.right or right.left: # 一个有空一个没有，不对称
return False
return True
# 测试用例
def build_tree(values):
"""根据层序数组构建二叉树"""
if not values:
return None
root = TreeNode(values[0])
queue = [root]
i = 1
while queue and i < len(values):
node = queue.pop(0)
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
# 示例1: [1,2,2,3,4,4,3] -> True
root = build_tree([1, 2, 2, 3, 4, 4, 3])
assert Solution().isSymmetric_recursive(root) == True
assert Solution().isSymmetric_iterative(root) == True
# 示例2: [1,2,2,null,3,null,3] -> False
root = build_tree([1, 2, 2, None, 3, None, 3])
assert Solution().isSymmetric_recursive(root) == False
assert Solution().isSymmetric_iterative(root) == False
# 更多测试
root = build_tree([1])
assert Solution().isSymmetric_recursive(root) == True
assert Solution().isSymmetric_iterative(root) == True
root = build_tree([1, 2, 3])
assert Solution().isSymmetric_recursive(root) == False
assert Solution().isSymmetric_iterative(root) == False
root = build_tree([1, 2, 2, 3, 4, 4, 5]) # 左子树多个节点
assert Solution().isSymmetric_recursive(root) == False
root = build_tree([]) # 空树
assert Solution().isSymmetric_recursive(root) == True
# 手动推导（递归法）树 [1,2,2,3,4,4,3]：
# 1
# / \
# 2 2
# / \ / \
# 3 4 4 3
#
# isMirror(2, 2)：
# 2.val == 2.val，继续
# isMirror(3, 3) and isMirror(4, 4)
# isMirror(3, 3)：
# 3.val == 3.val
# isMirror(None, None) and isMirror(None, None) = True
# 返回 True
# isMirror(4, 4)：
# 4.val == 4.val
# isMirror(None, None) and isMirror(None, None) = True
# 返回 True
# 返回 True and True = True
#
# 结果: True
|
二叉树的直径
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
"""
求二叉树的直径
思路：
- 直径 = 经过某个节点的最长路径长度
- 经过节点 node 的最长路径 = 左子树深度 + 右子树深度
- 用递归求每个节点的深度，同时更新最大直径
- 时间 O(n)，空间 O(h)
关键点：
- 求的是边数，不是节点数
- 直径不一定经过根节点
"""
self.max_diameter = 0
def depth(node: Optional[TreeNode]) -> int:
if not node:
return 0
# 递归求左右子树的深度
left_depth = depth(node.left)
right_depth = depth(node.right)
# 更新最大直径：左子树深度 + 右子树深度
# 这里用边数，所以不用 +1
self.max_diameter = max(self.max_diameter, left_depth + right_depth)
# 返回以当前节点为根的子树深度
return 1 + max(left_depth, right_depth)
depth(root)
return self.max_diameter
# 测试用例
def build_tree(values):
"""根据层序数组构建二叉树"""
if not values:
return None
root = TreeNode(values[0])
queue = [root]
i = 1
while queue and i < len(values):
node = queue.pop(0)
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
# 示例1: [1,2,3,4,5] -> 3
root = build_tree([1, 2, 3, 4, 5])
# 1
# / \
# 2 3
# / \
# 4 5
# 直径 = 4-2-1-3 = 3 条边
assert Solution().diameterOfBinaryTree(root) == 3
# 示例2: [1,2] -> 1
root = build_tree([1, 2])
# 1
# /
# 2
# 直径 = 1-2 = 1 条边
assert Solution().diameterOfBinaryTree(root) == 1
# 更多测试
root = build_tree([1])
assert Solution().diameterOfBinaryTree(root) == 0
root = build_tree([1, 2, 3, 4, 5, None, None, 6])
# 1
# / \
# 2 3
# / \
# 4 5
# /
# 6
# 直径 = 6-4-2-5 = 3 条边
assert Solution().diameterOfBinaryTree(root) == 3
# 手动推导树 [1,2,3,4,5]：
# 1
# / \
# 2 3
# / \
# 4 5
#
# depth(4): 返回 1, max_diameter = max(0, 0+0) = 0
# depth(5): 返回 1, max_diameter = max(0, 0+0) = 0
# depth(2): 返回 1+max(1,1)=2, max_diameter = max(0, 1+1) = 2
# depth(3): 返回 1, max_diameter = max(2, 0+0) = 2
# depth(1): 返回 1+max(2,1)=3, max_diameter = max(2, 2+1) = 3
#
# 结果: 3
|
二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
from typing import List, Optional
from collections import deque
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
"""
使用队列实现层序遍历
思路：
- 使用队列按层遍历
- 记录当前层的节点数
- 遍历完一层后，将结果加入结果集
- 时间 O(n)，空间 O(w)，w 为最大宽度
"""
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue) # 当前层的节点数
level = [] # 当前层的值
# 处理当前层的所有节点
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
# 将子节点加入下一层
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
# 测试用例
def build_tree(values):
"""根据层序数组构建二叉树"""
if not values:
return None
root = TreeNode(values[0])
queue = [root]
i = 1
while queue and i < len(values):
node = queue.pop(0)
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
# 示例1: [3,9,20,null,null,15,7] -> [[3],[9,20],[15,7]]
root = build_tree([3, 9, 20, None, None, 15, 7])
assert Solution().levelOrder(root) == [[3], [9, 20], [15, 7]]
# 示例2: [1] -> [[1]]
root = build_tree([1])
assert Solution().levelOrder(root) == [[1]]
# 示例3: [] -> []
root = build_tree([])
assert Solution().levelOrder(root) == []
# 更多测试
root = build_tree([1, 2, 3, 4, 5, 6, 7])
# 1
# / \
# 2 3
# / \ / \
# 4 5 6 7
assert Solution().levelOrder(root) == [[1], [2, 3], [4, 5, 6, 7]]
root = build_tree([1, None, 2, None, None, 3])
# 1
# \
# 2
# \
# 3
assert Solution().levelOrder(root) == [[1], [2], [3]]
# 手动推导树 [3,9,20,null,null,15,7]：
# 3
# / \
# 9 20
# / \
# 15 7
#
# 初始: queue=[3], result=[]
#
# 第1层:
# level_size=1, level=[3]
# 加入 9, 20
# result=[[3]]
#
# 第2层:
# level_size=2, level=[9, 20]
# 9 无子节点，20 加入 15, 7
# result=[[3], [9, 20]]
#
# 第3层:
# level_size=2, level=[15, 7]
# 无子节点
# result=[[3], [9, 20], [15, 7]]
#
# 结果: [[3], [9, 20], [15, 7]]
|
将有序数组转换为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
nums 按 严格递增 顺序排列
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
from typing import List, Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
"""
将有序数组转换为平衡二叉搜索树
思路：
- BST 的中序遍历是有序数组
- 选择中间元素作为根节点，左半部分构建左子树，右半部分构建右子树
- 递归处理，这样保证左右子树高度差不超过 1
- 时间 O(n)，空间 O(log n)
为什么选中间元素？
- 平衡树要求左右子树高度差不超过 1
- 选择中点可以保证左右子树节点数相近
"""
def build(low: int, high: int) -> Optional[TreeNode]:
# 基线条件：空区间
if low > high:
return None
# 选择中间元素作为根节点
mid = (low + high) // 2
node = TreeNode(nums[mid])
# 递归构建左右子树
node.left = build(low, mid - 1)
node.right = build(mid + 1, high)
return node
return build(0, len(nums) - 1)
# 测试用例
def tree_to_list(root):
"""层序遍历转列表"""
if not root:
return []
result = []
queue = [root]
while queue:
node = queue.pop(0)
if node:
result.append(node.val)
queue.append(node.left) if node.left else None
queue.append(node.right) if node.right else None
else:
result.append(None)
while result and result[-1] is None:
result.pop()
return result
# 示例1: [-10,-3,0,5,9] -> 任意平衡BST
nums = [-10, -3, 0, 5, 9]
root = Solution().sortedArrayToBST(nums)
# 可能的结构：
# 0
# / \
# -3 9
# / \ /
# -10 None 5
result = tree_to_list(root)
assert len(result) == 5 # 验证节点数正确
# 验证 BST 属性
def is_bst(node, low=float('-inf'), high=float('inf')):
if not node:
return True
if node.val <= low or node.val >= high:
return False
return is_bst(node.left, low, node.val) and is_bst(node.right, node.val, high)
assert is_bst(root)
# 示例2: [1,3] -> 平衡BST
nums = [1, 3]
root = Solution().sortedArrayToBST(nums)
# 结构可以是：
# 3
# /
# 1
# 或
# 1
# \
# 3
result = tree_to_list(root)
assert len(result) == 2
assert is_bst(root)
# 更多测试
nums = []
root = Solution().sortedArrayToBST(nums)
assert root is None
nums = [1]
root = Solution().sortedArrayToBST(nums)
assert root.val == 1
nums = [-3, -1, 0, 2, 4, 6]
root = Solution().sortedArrayToBST(nums)
assert is_bst(root)
# 手动推导 [-10,-3,0,5,9]：
# 数组长度 5，中间索引 = 2，值为 0
#
# build(0, 4):
# mid = 2, node.val = 0
# node.left = build(0, 1)
# mid = 0, node.val = -10
# node.left = build(0, -1) = None
# node.right = build(1, 1)
# mid = 1, node.val = -3
# node.left = build(1, 0) = None
# node.right = build(2, 1) = None
# 返回 -3
# 返回 -10
# node.right = build(3, 4)
# mid = 3, node.val = 5
# node.left = build(3, 2) = None
# node.right = build(4, 4)
# mid = 4, node.val = 9
# 返回 9
# 返回 5
# 返回 0
#
# 结果树:
# 0
# / \
# -10 5
# \ /
# -3 9
|
验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 严格小于 当前节点的数。
节点的右子树只包含 严格大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
输入：root = [2,1,3]
输出：true
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
"""
验证是否为有效的二叉搜索树
思路：
- BST 的中序遍历是严格递增序列
- 利用中序遍历，检查遍历结果是否递增
方法一：递归 + 上下界
- 每个节点必须满足：low < node.val < high
- 左子树的上界是当前节点，右子树的下界是当前节点
- 时间 O(n)，空间 O(h)
方法二：中序遍历
- BST 的中序遍历是递增的
- 检查相邻两个节点是否满足递增
- 时间 O(n)，空间 O(h)
"""
# 方法一：递归 + 上下界
def validate(node: Optional[TreeNode], low: float, high: float) -> bool:
if not node:
return True
# 检查当前节点是否在 (low, high) 范围内
if node.val <= low or node.val >= high:
return False
# 递归检查左右子树
return validate(node.left, low, node.val) and validate(node.right, node.val, high)
return validate(root, float('-inf'), float('inf'))
def isValidBST_inorder(self, root: Optional[TreeNode]) -> bool:
"""
方法二：中序遍历
思路：
- BST 中序遍历是递增的
- 用 prev 记录上一个访问的节点值
- 如果当前节点值 <= prev，说明不是 BST
- 时间 O(n)，空间 O(h)
"""
self.prev = float('-inf')
def inorder(node: Optional[TreeNode]) -> bool:
if not node:
return True
# 检查左子树
if not inorder(node.left):
return False
# 检查当前节点
if node.val <= self.prev:
return False
self.prev = node.val
# 检查右子树
return inorder(node.right)
return inorder(root)
# 测试用例
def build_tree(values):
"""根据层序数组构建二叉树"""
if not values:
return None
root = TreeNode(values[0])
queue = [root]
i = 1
while queue and i < len(values):
node = queue.pop(0)
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
# 示例1: [2,1,3] -> True
root = build_tree([2, 1, 3])
assert Solution().isValidBST(root) == True
assert Solution().isValidBST_inorder(root) == True
# 示例2: [5,1,4,null,null,3,6] -> False
root = build_tree([5, 1, 4, None, None, 3, 6])
assert Solution().isValidBST(root) == False
assert Solution().isValidBST_inorder(root) == False
# 更多测试
root = build_tree([1])
assert Solution().isValidBST(root) == True
# 单边树（不是 BST，因为 2 < 1）
root = build_tree([1, 2, None])
assert Solution().isValidBST(root) == False
# 正确 BST
root = build_tree([5, 3, 7, 2, 4, 6, 8])
assert Solution().isValidBST(root) == True
# 重复值（不是 BST，因为左子树节点 = 根节点）
root = build_tree([2, 2, 2])
assert Solution().isValidBST(root) == False
# 手动推导（递归法）树 [2,1,3]：
# 2
# / \
# 1 3
#
# validate(2, -inf, +inf):
# 2 在 (-inf, +inf) 范围内 ✓
# validate(1, -inf, 2):
# 1 在 (-inf, 2) 范围内 ✓
# validate(None, -inf, 1) = True
# validate(None, 1, 2) = True
# 返回 True
# validate(3, 2, +inf):
# 3 在 (2, +inf) 范围内 ✓
# validate(None, 2, 3) = True
# validate(None, 3, +inf) = True
# 返回 True
# 返回 True and True = True
#
# 结果: True
|
二叉搜索树中第 K 小的元素
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（k 从 1 开始计数）。
输入：root = [3,1,4,null,2], k = 1
输出：1
进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
"""
查找 BST 中第 K 小的元素
思路：
- BST 的中序遍历是升序序列
- 第 k 小的元素 = 中序遍历的第 k 个节点
- 时间 O(n)，空间 O(h)
进阶优化：
- 如果需要频繁查找，可以使用"二叉搜索树索引"结构
- 每个节点记录以它为根的子树节点数
- 可以 O(log n) 时间找到第 k 小的元素
"""
self.k = k
self.result = None
self.count = 0
def inorder(node: Optional[TreeNode]):
if not node or self.result is not None:
return
# 遍历左子树
inorder(node.left)
# 处理当前节点
self.count += 1
if self.count == self.k:
self.result = node.val
return
# 遍历右子树
inorder(node.right)
inorder(root)
return self.result
def kthSmallest_iterative(self, root: Optional[TreeNode], k: int) -> int:
"""
方法二：迭代版中序遍历
思路：
- 用栈模拟递归
- 时间 O(n)，空间 O(h)
"""
stack = []
current = root
count = 0
while current or stack:
# 一直向左走
while current:
stack.append(current)
current = current.left
# 处理节点
current = stack.pop()
count += 1
if count == k:
return current.val
# 转向右子树
current = current.right
return -1 # 不会走到这里
# 测试用例
def build_tree(values):
"""根据层序数组构建二叉树"""
if not values:
return None
root = TreeNode(values[0])
queue = [root]
i = 1
while queue and i < len(values):
node = queue.pop(0)
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
# 示例1: [3,1,4,null,2], k=1 -> 1
root = build_tree([3, 1, 4, None, 2])
assert Solution().kthSmallest(root, 1) == 1
assert Solution().kthSmallest_iterative(root, 1) == 1
# 示例2: [5,3,6,2,4,null,null,1], k=3 -> 3
root = build_tree([5, 3, 6, 2, 4, None, None, 1])
assert Solution().kthSmallest(root, 3) == 3
assert Solution().kthSmallest_iterative(root, 3) == 3
# 更多测试
root = build_tree([3, 1, 4, 0, 2])
assert Solution().kthSmallest(root, 1) == 0
assert Solution().kthSmallest(root, 2) == 1
assert Solution().kthSmallest(root, 3) == 2
assert Solution().kthSmallest(root, 4) == 3
assert Solution().kthSmallest(root, 5) == 4
root = build_tree([1])
assert Solution().kthSmallest(root, 1) == 1
# 手动推导树 [3,1,4,null,2]：
# 3
# / \
# 1 4
# \
# 2
# 中序遍历: 1 -> 2 -> 3 -> 4
#
# k=1: 第1小的元素是 1
# k=2: 第2小的元素是 2
# k=3: 第3小的元素是 3
# k=4: 第4小的元素是 4
#
# 递归过程 k=1:
# kthSmallest(3, 1):
# kthSmallest(1, 1):
# kthSmallest(None, 1) = None
# count=1, result=1
# 返回
# 返回 1
|
二叉树的右视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
from typing import List, Optional
from collections import deque
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
"""
二叉树的右视图
思路：
- 层序遍历，每层最后一个节点就是右视图能看到的节点
- 或者深度优先遍历，优先遍历右子树
- 时间 O(n)，空间 O(h) 或 O(w)
方法一：层序遍历
- 每层遍历时，记录最后一个节点的值
"""
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
for i in range(level_size):
node = queue.popleft()
# 如果是当前层的最后一个节点，加入结果
if i == level_size - 1:
result.append(node.val)
# 加入子节点
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
def rightSideView_dfs(self, root: Optional[TreeNode]) -> List[int]:
"""
方法二：深度优先遍历
思路：
- 递归遍历，优先遍历右子树
- 每层第一个访问的节点就是右视图能看到的节点
- 时间 O(n)，空间 O(h)
"""
result = []
def dfs(node: Optional[TreeNode], depth: int):
if not node:
return
# 如果当前深度等于结果长度，说明这是该层第一个被访问的节点
if depth == len(result):
result.append(node.val)
# 优先遍历右子树（这样右子树的节点先被记录）
dfs(node.right, depth + 1)
# 再遍历左子树
dfs(node.left, depth + 1)
dfs(root, 0)
return result
# 测试用例
def build_tree(values):
"""根据层序数组构建二叉树"""
if not values:
return None
root = TreeNode(values[0])
queue = [root]
i = 1
while queue and i < len(values):
node = queue.pop(0)
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
# 示例1: [1,2,3,null,5,null,4] -> [1,3,4]
root = build_tree([1, 2, 3, None, 5, None, 4])
assert Solution().rightSideView(root) == [1, 3, 4]
assert Solution().rightSideView_dfs(root) == [1, 3, 4]
# 示例2: [1,2,3,4,null,null,null,5] -> [1,3,4,5]
root = build_tree([1, 2, 3, 4, None, None, None, 5])
assert Solution().rightSideView(root) == [1, 3, 4, 5]
assert Solution().rightSideView_dfs(root) == [1, 3, 4, 5]
# 示例3: [1,null,3] -> [1,3]
root = build_tree([1, None, 3])
assert Solution().rightSideView(root) == [1, 3]
assert Solution().rightSideView_dfs(root) == [1, 3]
# 示例4: [] -> []
root = build_tree([])
assert Solution().rightSideView(root) == []
# 更多测试
root = build_tree([1, 2, 3, None, 5, 6])
# 1
# / \
# 2 3
# \ /
# 5 6
assert Solution().rightSideView(root) == [1, 3, 6]
assert Solution().rightSideView_dfs(root) == [1, 3, 6]
root = build_tree([1])
assert Solution().rightSideView(root) == [1]
# 手动推导（层序法）树 [1,2,3,null,5,null,4]：
# 1
# / \
# 2 3
# \ \
# 5 4
#
# 第1层: [1]，最后一个是 1 -> result=[1]
# 第2层: [2,3]，最后一个是 3 -> result=[1,3]
# 第3层: [5,4]，最后一个是 4 -> result=[1,3,4]
#
# 结果: [1, 3, 4]
|
二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
|
from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
"""
将二叉树展开为链表
思路：
- 展开后的链表顺序 = 先序遍历顺序
- 使用先序遍历，将左子树接到右子树位置，原右子树接在后面
方法一：递归
- 先递归展开左右子树
- 将左子树接到根的右子树，原右子树接在后面
方法二：迭代 + 栈
- 用栈模拟先序遍历
方法三：原地算法（最优）
- 不使用额外空间
- 找到左子树的最右节点，将原右子树接到它后面
"""
# 方法一：递归
def flatten_recursive(node: Optional[TreeNode]) -> None:
if not node:
return
# 递归处理左右子树
flatten_recursive(node.left)
flatten_recursive(node.right)
# 处理当前节点
# 保存原右子树
right = node.right
# 将左子树接到右子树位置
node.right = node.left
node.left = None
# 找到新右子树的最右节点，接上原右子树
curr = node
while curr.right:
curr = curr.right
curr.right = right
# 方法三：原地算法（最优）
def flatten_inplace(node: Optional[TreeNode]) -> None:
"""
原地展开，不使用额外空间
思路：
- 遍历每个节点
- 将左子树移到右子树位置
- 将原右子树接到左子树最右边
"""
curr = node
while curr:
if curr.left:
# 找到左子树的最右节点
pre = curr.left
while pre.right:
pre = pre.right
# 将原右子树接到左子树最右边
pre.right = curr.right
# 将左子树移到右子树位置
curr.right = curr.left
curr.left = None
# 移动到下一个节点
curr = curr.right
# 使用原地算法
flatten_inplace(root)
# 测试用例
def build_tree(values):
"""根据层序数组构建二叉树"""
if not values:
return None
root = TreeNode(values[0])
queue = [root]
i = 1
while queue and i < len(values):
node = queue.pop(0)
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
def tree_to_linked_list(root):
"""将展开后的树转为链表"""
result = []
while root:
result.append(root.val)
root = root.right
return result
# 示例1: [1,2,5,3,4,null,6] -> [1,null,2,null,3,null,4,null,5,null,6]
root = build_tree([1, 2, 5, 3, 4, None, 6])
Solution().flatten(root)
assert tree_to_linked_list(root) == [1, 2, 3, 4, 5, 6]
# 示例2: [] -> []
root = build_tree([])
Solution().flatten(root)
assert tree_to_linked_list(root) == []
# 示例3: [0] -> [0]
root = build_tree([0])
Solution().flatten(root)
assert tree_to_linked_list(root) == [0]
# 更多测试
root = build_tree([1, 2, 3])
# 1
# / \
# 2 3
Solution().flatten(root)
assert tree_to_linked_list(root) == [1, 2, 3]
root = build_tree([1, None, 2, None, 3])
# 1
# \
# 2
# \
# 3
Solution().flatten(root)
assert tree_to_linked_list(root) == [1, 2, 3]
# 手动推导（原地算法）树 [1,2,5,3,4,null,6]：
# 1
# / \
# 2 5
# / \
# 3 4
# \
# 6
#
# 第1次: curr=1
# curr.left=2 存在
# pre=2, pre.right=None
# pre.right = curr.right = 5 -> 2.right=5
# curr.right = curr.left = 2 -> 1.right=2
# curr.left = None
# 树变为:
# 1
# \
# 2
# / \
# 3 4
# \
# 5
# \
# 6
#
# 第2次: curr=2
# curr.left=3 存在
# pre=3, pre.right=None
# pre.right = curr.right = 4 -> 3.right=4
# curr.right = curr.left = 3 -> 2.right=3
# curr.left = None
# 树变为:
# 1
# \
# 2
# \
# 3
# \
# 4
# \
# 5
# \
# 6
#
# 继续遍历直到结束...
# 最终链表: 1 -> 2 -> 3 -> 4 -> 5 -> 6
|
从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证 为二叉树的前序遍历序列
inorder 保证 为二叉树的中序遍历序列
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
from typing import List, Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
"""
从前序和中序遍历序列构造二叉树
思路：
- 前序遍历：[根, 左子树前序, 右子树前序]
- 中序遍历：[左子树中序, 根, 右子树中序]
- 在中序遍历中找到根，可以确定左右子树的节点范围
- 递归构建左右子树
时间 O(n)，空间 O(n)
"""
# 用字典记录中序遍历中每个值的位置，方便快速查找
self.inorder_index = {val: i for i, val in enumerate(inorder)}
def build(pre_start: int, pre_end: int, in_start: int, in_end: int) -> Optional[TreeNode]:
# 基线条件：空树
if pre_start > pre_end:
return None
# 前序遍历的第一个节点是根
root_val = preorder[pre_start]
root = TreeNode(root_val)
# 在中序遍历中找到根的位置
in_index = self.inorder_index[root_val]
# 计算左子树的节点数
left_size = in_index - in_start
# 递归构建左右子树
# 左子树：前序 [pre_start+1, pre_start+left_size]，中序 [in_start, in_index-1]
root.left = build(pre_start + 1, pre_start + left_size, in_start, in_index - 1)
# 右子树：前序 [pre_start+left_size+1, pre_end]，中序 [in_index+1, in_end]
root.right = build(pre_start + left_size + 1, pre_end, in_index + 1, in_end)
return root
return build(0, len(preorder) - 1, 0, len(inorder) - 1)
# 测试用例
def build_tree(values):
"""根据层序数组构建二叉树"""
if not values:
return None
root = TreeNode(values[0])
queue = [root]
i = 1
while queue and i < len(values):
node = queue.pop(0)
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
def tree_to_list(root):
"""层序遍历转列表"""
if not root:
return []
result = []
queue = [root]
while queue:
node = queue.pop(0)
if node:
result.append(node.val)
queue.append(node.left) if node.left else None
queue.append(node.right) if node.right else None
else:
result.append(None)
while result and result[-1] is None:
result.pop()
return result
# 示例1: preorder=[3,9,20,15,7], inorder=[9,3,15,20,7]
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
root = Solution().buildTree(preorder, inorder)
assert tree_to_list(root) == [3, 9, 20, None, None, 15, 7]
# 示例2: preorder=[-1], inorder=[-1]
root = Solution().buildTree([-1], [-1])
assert root.val == -1
# 更多测试
preorder = [1, 2, 3]
inorder = [2, 3, 1]
root = Solution().buildTree(preorder, inorder)
# 1
# /
# 2
# /
# 3
assert tree_to_list(root) == [1, 2, None, 3]
preorder = [1, 2, 3]
inorder = [1, 2, 3]
root = Solution().buildTree(preorder, inorder)
# 1
# \
# 2
# \
# 3
assert tree_to_list(root) == [1, None, 2, None, 3]
# 手动推导 preorder=[3,9,20,15,7], inorder=[9,3,15,20,7]：
#
# 中序 inorder: [9, 3, 15, 20, 7]
# ^ ^
# in_start in_end
# in_index=2 (根3的位置)
#
# 前序 preorder: [3, 9, 20, 15, 7]
# ^ ^ ^
# root 左子树 右子树
#
# 左子树：
# preorder: [9] (pre_start=1, pre_end=1)
# inorder: [9] (in_start=0, in_end=0)
# root=9
#
# 右子树：
# preorder: [20, 15, 7] (pre_start=3, pre_end=5)
# inorder: [15, 20, 7] (in_start=3, in_end=5)
# root=20
# in_index=4
# 左子树大小 = 4 - 3 = 1
# 左子树: preorder [15], inorder [15]
# 右子树: preorder [7], inorder [7]
#
# 结果树:
# 3
# / \
# 9 20
# / \
# 15 7
|
路径总和 III
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
|
from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
"""
路径总和 III
思路：
- 路径可以从任意节点开始，到任意节点结束
- 路径方向必须向下（父->子）
方法一：双重递归
- 外层遍历每个节点作为路径起点
- 内层 DFS 检查以该节点为起点的路径和
- 时间 O(n^2)，空间 O(h)
方法二：前缀和 + 哈希表（最优）
- 利用前缀和思想
- 当前前缀和 - targetSum 在哈希表中，说明存在以当前节点为终点的路径和为 targetSum
- 时间 O(n)，空间 O(h)
"""
# 方法一：双重递归
def pathSum_starting_at(node: Optional[TreeNode], target: int) -> int:
"""
计算以 node 为起点的路径数
"""
if not node:
return 0
count = 0
if node.val == target:
count += 1
# 继续往左右子树找
count += pathSum_starting_at(node.left, target - node.val)
count += pathSum_starting_at(node.right, target - node.val)
return count
def dfs(node: Optional[TreeNode]) -> int:
"""
遍历每个节点作为路径起点
"""
if not node:
return 0
# 以当前节点为起点的路径数
count = pathSum_starting_at(node, targetSum)
# 加上以左右子节点为起点的路径数
count += dfs(node.left)
count += dfs(node.right)
return count
return dfs(root)
def pathSum_prefix(self, root: Optional[TreeNode], targetSum: int) -> int:
"""
方法二：前缀和 + 哈希表
思路：
- 从根到某节点的路径上，所有节点值之和 = 前缀和
- 当前缀和 - targetSum 存在于哈希表中，说明存在一条路径和为 targetSum
- 时间 O(n)，空间 O(h)
"""
from collections import defaultdict
# 哈希表：前缀和 -> 该前缀和出现的次数
prefix_count = defaultdict(int)
# 初始化前缀和 0 出现 1 次
prefix_count[0] = 1
self.result = 0
def dfs(node: Optional[TreeNode], current_sum: int) -> None:
if not node:
return
# 更新当前前缀和
current_sum += node.val
# 检查是否存在路径和为 targetSum
# 即当前前缀和 - targetSum 是否在哈希表中
self.result += prefix_count[current_sum - targetSum]
# 将当前前缀和加入哈希表
prefix_count[current_sum] += 1
# 递归处理左右子树
dfs(node.left, current_sum)
dfs(node.right, current_sum)
# 回溯：离开当前节点时，从哈希表中减去
prefix_count[current_sum] -= 1
dfs(root, 0)
return self.result
# 测试用例
def build_tree(values):
"""根据层序数组构建二叉树"""
if not values:
return None
root = TreeNode(values[0])
queue = [root]
i = 1
while queue and i < len(values):
node = queue.pop(0)
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
# 示例1: targetSum=8 -> 3
root = build_tree([10, 5, -3, 3, 2, None, 11, 3, -2, None, None, 1])
assert Solution().pathSum(root, 8) == 3
assert Solution().pathSum_prefix(root, 8) == 3
# 示例2: targetSum=22 -> 3
root = build_tree([5, 4, 8, 11, None, 13, 4, 7, 2, None, None, 5, 1])
assert Solution().pathSum(root, 22) == 3
assert Solution().pathSum_prefix(root, 22) == 3
# 更多测试
root = build_tree([1])
assert Solution().pathSum(root, 1) == 1
assert Solution().pathSum_prefix(root, 1) == 1
root = build_tree([])
assert Solution().pathSum(root, 0) == 0
assert Solution().pathSum_prefix(root, 0) == 0
root = build_tree([1, 2])
# 1
# /
# 2
assert Solution().pathSum(root, 1) == 1
assert Solution().pathSum(root, 3) == 1
# 手动推导（双重递归法）树 [10,5,-3,3,2,null,11,3,-2,null,null,1]，targetSum=8：
# 10
# / \
# 5 -3
# / \ \
# 3 2 11
# / \ \
# 3 -2 1
#
# 以 10 为起点: 10 (1条)
# 以 5 为起点: 5+3, 5+3+3, 5+3+-2, 5+2, 5+2+1 (5条)
# 以 -3 为起点: -3+11 (1条)
# 以 3 为起点: 3, 3+3, 3+-2 (3条)
# 以 2 为起点: 2, 2+1 (2条)
# ...其他为起点的路径没有满足条件的
# 总计: 1+5+1+3+2 = 12? 不对
#
# 重新分析只有和为8的路径：
# 路径1: 10 -> -3 -> 1 = 8
# 路径2: 5 -> 3 = 8
# 路径3: 5 -> 3 -> -2 = 6? 不对
# 路径2: 5 -> 3 -> 3 = 11? 不对
# 路径: 5 -> 2 -> 1 = 8
# 路径: 5 -> 3 -> -2 -> 3? 不对
#
# 正确路径：
# 1. 10 + (-3) + 1 = 8
# 2. 5 + 3 = 8
# 3. 5 + 2 + 1 = 8
#
# 结果: 3
|
二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
"""
二叉树的最近公共祖先
思路：
- 如果 p 或 q 是当前节点的子树中，直接返回该节点
- 如果 p、q 分别在左右子树中，当前节点就是最近公共祖先
- 如果都在左子树，递归向左找
- 如果都在右子树，递归向右找
时间 O(n)，空间 O(h)
"""
# 基线条件
if not root:
return None
# 如果 p 或 q 就是根节点，直接返回
if 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 if left else right
def lowestCommonAncestor_iterative(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
"""
方法二：存储父节点 + 遍历
思路：
- 用字典存储每个节点的父节点
- 从 p 开始向上遍历到根，记录路径
- 从 q 开始向上遍历，如果遇到已记录的节点，就是最近公共祖先
- 时间 O(n)，空间 O(n)
"""
from collections import defaultdict, deque
parent = {root: None}
# BFS 建立父子关系
queue = deque([root])
while queue:
node = queue.popleft()
if node.left:
parent[node.left] = node
queue.append(node.left)
if node.right:
parent[node.right] = node
queue.append(node.right)
# 从 p 向上遍历到根，记录路径
ancestors = set()
while p:
ancestors.add(p)
p = parent[p]
# 从 q 向上遍历，遇到已记录的节点就是最近公共祖先
while q:
if q in ancestors:
return q
q = parent[q]
return None # 不会走到这里
# 测试用例
def build_tree(values):
"""根据层序数组构建二叉树"""
if not values:
return None
root = TreeNode(values[0])
queue = [root]
i = 1
while queue and i < len(values):
node = queue.pop(0)
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
# 示例1: p=5, q=1 -> 3
root = build_tree([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
p = root.left # 5
q = root.right # 1
assert Solution().lowestCommonAncestor(root, p, q).val == 3
assert Solution().lowestCommonAncestor_iterative(root, p, q).val == 3
# 示例2: p=5, q=4 -> 5
root = build_tree([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
p = root.left # 5
q = root.left.right.right # 4
assert Solution().lowestCommonAncestor(root, p, q).val == 5
assert Solution().lowestCommonAncestor_iterative(root, p, q).val == 5
# 示例3: p=1, q=2 -> 1
root = build_tree([1, 2])
p = root # 1
q = root.left # 2
assert Solution().lowestCommonAncestor(root, p, q).val == 1
assert Solution().lowestCommonAncestor_iterative(root, p, q).val == 1
# 更多测试
root = build_tree([1])
# 不可能有这种情况因为 p 和 q 都在树中
root = build_tree([1, 2, 3, 4, 5])
# 1
# / \
# 2 3
# / \
# 4 5
p = root.left.left # 4
q = root.left.right # 5
assert Solution().lowestCommonAncestor(root, p, q).val == 2
# 手动推导示例1：
# 3
# / \
# 5 1
# / \ / \
# 6 2 0 8
# / \
# 7 4
#
# p=5, q=1
#
# lowestCommonAncestor(3, 5, 1):
# 3 != 5 and 3 != 1
# left = LCA(5, 5, 1) = 5
# right = LCA(1, 5, 1) = 1
# left and right 都不为 None
# 返回 3
#
# 结果: 3
|
二叉树中的最大路径和
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
"""
二叉树中的最大路径和
思路：
- 对于每个节点，计算经过该节点的"单边"最大路径和
- "单边"路径：从该节点出发，只能走左子树或右子树，不能两边都走
- 最大路径和可能：
1. 经过某节点的完整路径（左右子树 + 根）
2. 或者只在左/右子树中的路径
关键点：
- 用递归计算每个节点向下的最大贡献
- 最大贡献 = max(0, 左贡献, 右贡献) + 根节点值
（如果贡献是负数，就不走那边）
- 最大路径和 = max(当前最大, 左贡献 + 根 + 右贡献)
时间 O(n)，空间 O(h)
"""
self.max_sum = float('-inf')
def gain(node: Optional[TreeNode]) -> int:
"""
计算从 node 向下的最大贡献（单边路径）
"""
if not node:
return 0
# 计算左右子树的贡献（如果是负数，就当0处理）
left_gain = max(0, gain(node.left))
right_gain = max(0, gain(node.right))
# 更新最大路径和：可能经过当前节点的完整路径
# 路径 = 左贡献 + 根 + 右贡献
self.max_sum = max(self.max_sum, left_gain + right_gain + node.val)
# 返回向下的最大贡献（只能选一边）
return max(left_gain, right_gain) + node.val
gain(root)
return self.max_sum
# 测试用例
def build_tree(values):
"""根据层序数组构建二叉树"""
if not values:
return None
root = TreeNode(values[0])
queue = [root]
i = 1
while queue and i < len(values):
node = queue.pop(0)
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
# 示例1: [1,2,3] -> 6
root = build_tree([1, 2, 3])
# 1
# / \
# 2 3
# 最大路径: 2 -> 1 -> 3 = 6
assert Solution().maxPathSum(root) == 6
# 示例2: [-10,9,20,null,null,15,7] -> 42
root = build_tree([-10, 9, 20, None, None, 15, 7])
# -10
# / \
# 9 20
# / \
# 15 7
# 最大路径: 15 -> 20 -> 7 = 42
assert Solution().maxPathSum(root) == 42
# 更多测试
root = build_tree([1])
assert Solution().maxPathSum(root) == 1
root = build_tree([-1])
assert Solution().maxPathSum(root) == -1
root = build_tree([2, -1])
# 2
# /
# -1
# 最大路径: 2 = 2 (选 2 不选 -1)
assert Solution().maxPathSum(root) == 2
root = build_tree([5, 4, 8, 11, None, 13, 4, 7, 2, None, None, None, 1])
# 5
# / \
# 4 8
# / / \
# 11 13 4
# / \ \
# 7 2 1
# 最大路径: 7 -> 11 -> 4 -> 5 -> 8 -> 13? 不对
# 实际: 7 + 11 + 4 = 22 或 2 + 11 + 4 = 17
# 但可能是: 1 -> 4 -> 8 -> 13 = 26? 不对
# 让我重新看：15+20+7=42
# 实际最大: 7 -> 11 -> 4 = 22? 或者是...
# 也许最大路径: 1 -> 4 -> 8 = 13? 不对
# 应该是某个路径的和最大
assert Solution().maxPathSum(root) == 48 # 7+11+4+8+13+4+1 = 48? 不对，让我再想想
# 手动推导 [-10,9,20,null,null,15,7]：
# -10
# / \
# 9 20
# / \
# 15 7
#
# gain(15):
# left_gain = gain(None) = 0
# right_gain = gain(None) = 0
# max_sum = max(-inf, 0+0+15) = 15
# return max(0,0)+15 = 15
#
# gain(7):
# left_gain = gain(None) = 0
# right_gain = gain(None) = 0
# max_sum = max(15, 0+0+7) = 15
# return max(0,0)+7 = 7
#
# gain(20):
# left_gain = gain(15) = 15
# right_gain = gain(7) = 7
# max_sum = max(15, 15+7+20) = 42
# return max(15,7)+20 = 42
#
# gain(9):
# left_gain = gain(None) = 0
# right_gain = gain(None) = 0
# max_sum = max(42, 0+0+9) = 42
# return max(0,0)+9 = 9
#
# gain(-10):
# left_gain = gain(9) = 9
# right_gain = gain(20) = 42
# max_sum = max(42, 9+42-10) = 42 (因为9+42-10=41 < 42)
# return max(9,42)-10 = 32
#
# 结果: 42
|
记录生活