代码-二叉树¶
- 代码-二叉树
- 概述
- 题目
- 144. 二叉树的前序遍历
- 145. 二叉树的后序遍历
- 94. 二叉树的中序遍历
- 102. 二叉树的层序遍历
- 199.二叉树的右视图
- 637.二叉树的层平均值
- 429. N叉树的层序遍历
- 515. 在每个树行中找最大值
- 226. 翻转二叉树
- 101. 对称二叉树
- 104. 二叉树的最大深度
- 559. N叉树的最大深度
- 111. 二叉树的最小深度
- 222. 完全二叉树的节点个数
- 110. 平衡二叉树
- 257. 二叉树的所有路径
- 404. 左叶子之和
- 513. 找树左下角的值
- 112. 路径总和
- 106. 从后序与中序遍历序列构造二叉树
- 105. 从中序和前序遍历序列构造二叉树
- 654. 最大二叉树
- 617. 合并二叉树
- 700. 二叉搜索树中的搜索
- 98. 验证二叉搜索树
- 530. 二叉搜索树的最小绝对差
- 501. 二叉搜索树中的众数
- 236. 二叉树的最近公共祖先
- 235. 二叉搜索树的最近公共祖先
- 701. 二叉搜索树中的插入操作
概述¶
重点¶
- 需要记住的遍历方式：
| 前序遍历 | 后序遍历 | 中序遍历 | 层序遍历 | |
|---|---|---|---|---|
| 递归 | 直接递归 使用 dfs函数递归 |
直接递归 使用 dfs函数递归 |
直接递归 使用 dfs函数递归 |
使用bfs函数递归 |
| 迭代 | 不使用指针 使用指针的通用模板 |
不使用指针 使用指针的通用模板 |
使用指针的通用模板 | 使用deque/list迭代 |
- 递归需要熟练掌握，递归可以分为三步走：
- 首先确定递归函数的参数和返回值
- 然后确定递归的终止条件
- 最后需要确定单层递归的逻辑
二叉树题目易错点¶
- 需要注意二叉树节点数目是否可能为0，如果节点数目为0往往需要单独判断；
二叉树的种类¶
- 满二叉树：除了最后一层外其他层所有节点都包含两个子节点，且最后一层所有节点都没有子节点（深度为k的满二叉树包含\(2^k-1\)个节点）
- 完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 \([1, 2^{h-1}]\) 个节点。
- 二叉搜索树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树
- 平衡二叉搜索树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
二叉树的存储方式¶
- 链式存储：类似于链表，python定义二叉树：
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
- 顺序存储：等价于层序遍历，对于满二叉树，此时如果父节点的数组下标是
i，那么左右子节点的下标分别是2i+1和2i+2
二叉树的遍历方式¶
-
二叉树的遍历方式可以分为
深度优先搜索（depth-first search,DFS）和广度优先搜索（breadth-first search,BFS）两种，其中深度优先搜索包含前/中/后序遍历，这里前/中/后序遍历都是指父节点相对左右子节点的位置而言，例如前序对应中左右；广度优先搜索称为层序遍历；首先前/中/后序遍历可以采用递归和迭代的方式实现，其中递归实现时三种遍历代码形式类似，而采用迭代时有不同的实现方式；层序遍历同样也可以采用递归和迭代两种方式实现。 -
前/中/后序遍历
-
递归实现：用相似的递归代码形式可以实现前/中/后序遍历。当碰到空节点时返回，否则分别对左子节点和右子节点进行遍历，按照遍历顺序返回结果
# 第一种 # 前序遍历 class Solution: def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] left = self.preorderTraversal(root.left) right = self.preorderTraversal(root.right) return [root.val] + left + right # 中序遍历 class Solution: def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] left = self.inorderTraversal(root.left) right = self.inorderTraversal(root.right) return left + [root.val] + right # 后序遍历 class Solution: def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] left = self.postorderTraversal(root.left) right = self.postorderTraversal(root.right) return left + right + [root.val] # 第二种 # 前序遍历 class Solution: def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: def dfs(node): nonlocal res if not node: return res.append(node.val) dfs(node.left) dfs(node.right) res = [] dfs(root) return res # 考虑python的语言特性,函数传参过程中可迭代对象会被更改 class Solution: def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: def dfs(node, res): if not node: return res.append(node.val) dfs(node.left, res) dfs(node.right, res) res = [] dfs(root, res) return res # 中序遍历 class Solution: def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: def dfs(node): nonlocal res if not node: return dfs(node.left) res.append(node.val) dfs(node.right) res = [] dfs(root) return res # 考虑python的语言特性,函数传参过程中可迭代对象会被更改 class Solution: def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: def dfs(node, res): if not node: return dfs(node.left, res) res.append(node.val) dfs(node.right, res) res = [] dfs(root, res) return res # 后序遍历 class Solution: def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]: def dfs(node): nonlocal res if not node: return dfs(node.left) dfs(node.right) res.append(node.val) res = [] dfs(root) return res # 考虑python的语言特性,函数传参过程中可迭代对象会被更改 class Solution: def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]: def dfs(node, res): if not node: return dfs(node.left, res) dfs(node.right, res) res.append(node.val) res = [] dfs(root, res) return res -
迭代实现1：前序和后续代码形式类似，没有类似形式的中序遍历（因为后序相比前序就是左右节点入栈顺序改变，然后对返回列表翻转）。对于前序遍历，每次将当前节点添加到结果列表中，然后按照先加入右子节点再左子节点的方式将子节点加入到栈中。对于后续遍历，每次将当前节点添加到结果列表中，然后按照先加入左子节点再右子节点的方式将子节点加入到栈中，最后输出列表翻转。
# 前序遍历 class Solution: def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] res = [] stk = [root] while stk: node = stk.pop() res.append(node.val) if node.right: stk.append(node.right) if node.left: stk.append(node.left) return res # 后续遍历 class Solution: def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] res = [] stk = [root] while stk: node = stk.pop() res.append(node.val) if cur.left: stk.append(node.left) if node.right: stk.append(node.right) return res[::-1] -
迭代实现2：用相似的代码形式实现前/中/后序遍历。==利用指针==。对于前序遍历，如果指针非空，则不断把头节点加入结果列表中，并使指针指向左子节点；当指针指向空节点时，指针回退到头节点，并指向右子节点；当栈和指针都非空的时候，持续上述循环。后序遍历注意需要翻转列表，且子节点入栈顺序与前序遍历相反。==记下来（实在想不出来）==
# 前序遍历 class Solution: def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: res = [] stack = [] cur = root while stack or cur: while cur: res.append(cur.val) stack.append(cur) cur = cur.left cur = stack.pop() cur = cur.right return res # 中序遍历 class Solution: def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: res = [] stack = [] cur = root while stack or cur: while cur: stack.append(cur) cur = cur.left cur = stack.pop() res.append(cur.val) cur = cur.right return res # 后序遍历 class Solution: def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]: res = [] stack = [] cur = root while stack or cur: while cur: res.append(cur.val) stack.append(cur) cur = cur.right cur = stack.pop() cur = cur.left return res[::-1] -
迭代实现3：用相似的代码形式实现前/中/后序遍历。不使用指针，在遇到头节点后将None入栈，效果类似于指针。==也想不出来，不用记==
# 前序遍历 class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: res = [] stk = [] if root: stk.append(root) while stk: node = stk.pop() if node != None: if node.right: stk.append(node.right) if node.left: stk.append(node.left) stk.append(node) stk.append(None) else: node = stk.pop() res.append(node.val) return res # 中序遍历 class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: result = [] st = [] if root: st.append(root) while st: node = st.pop() if node != None: if node.right: #添加右节点（空节点不入栈） st.append(node.right) st.append(node) #添加中节点 st.append(None) #中节点访问过，但是还没有处理，加入空节点做为标记。 if node.left: #添加左节点（空节点不入栈） st.append(node.left) else: #只有遇到空节点的时候，才将下一个节点放进结果集 node = st.pop() #重新取出栈中元素 result.append(node.val) #加入到结果集 return result # 后序遍历 class Solution: def postorderTraversal(self, root: TreeNode) -> List[int]: result = [] st = [] if root: st.append(root) while st: node = st.pop() if node != None: st.append(node) #中 st.append(None) if node.right: #右 st.append(node.right) if node.left: #左 st.append(node.left) else: node = st.pop() result.append(node.val) return result -
层序遍历
-
递归实现：
class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: levels = [] self.bfs(root, 0, levels) return levels def bfs(self, node, level, levels): if not node: return if len(levels) == level: levels.append([]) levels[level].append(node.val) self.bfs(node.left, level + 1, levels) self.bfs(node.right, level + 1, levels) -
迭代实现1：使用队列
class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if not root: return [] queue = deque([root]) result = [] while queue: level = [] for _ in range(len(queue)): cur = queue.popleft() level.append(cur.val) if cur.left: queue.append(cur.left) if cur.right: queue.append(cur.right) result.append(level) return result -
迭代实现2：使用栈
class Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]: if not root: return [] cur_lay, res = [root], [] while cur_lay: lay, layval = [], [] for node in cur_lay: layval.append(node.val) if node.left: lay.append(node.left) if node.right: lay.append(node.right) cur_lay = lay res.append(layval) return res
题目¶
144. 二叉树的前序遍历¶
前序直接递归¶
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
left = self.preorderTraversal(root.left)
right = self.preorderTraversal(root.right)
return [root.val] + left + right
前序使用dfs递归¶
# 借助python函数传参特性
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def dfs(node, res):
if not node:
return
res.append(node.val)
dfs(node.left, res)
dfs(node.right, res)
res = []
dfs(root, res)
return res
# 利用nonlocal关键字
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def dfs(node):
nonlocal res
if not node:
return
res.append(node.val)
dfs(node.left)
dfs(node.right)
res = []
dfs(root)
return res
前序不使用指针迭代¶
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
stk, res = [root], []
while stk:
node = stk.pop()
res.append(node.val)
if node.right:
stk.append(node.right)
if node.left:
stk.append(node.left)
return res
前序使用指针迭代¶
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
cur, stk, res = root, [], []
while cur or stk:
while cur:
stk.append(cur)
res.append(cur.val)
cur = cur.left
cur = stk.pop()
cur = cur.right
return res
145. 二叉树的后序遍历¶
后序直接递归¶
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
left = self.postorderTraversal(root.left)
right = self.postorderTraversal(root.right)
return left + right + [root.val]
后序使用dfs递归¶
# 借助python函数传参特性
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def dfs(node, res):
if not node:
return
res.append(node.val)
dfs(node.right, res)
dfs(node.left, res)
res = []
dfs(root, res)
return res[::-1]
# 利用nonlocal关键字
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def dfs(node):
nonlocal res
if not node:
return
res.append(node.val)
dfs(node.right)
dfs(node.left)
res = []
dfs(root)
return res[::-1]
后序不使用指针迭代¶
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
stk, res = [root], []
while stk:
node = stk.pop()
res.append(node.val)
if node.left:
stk.append(node.left)
if node.right:
stk.append(node.right)
return res[::-1]
后序使用指针迭代¶
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
cur, stk, res = root, [], []
while cur or stk:
while cur:
stk.append(cur)
res.append(cur.val)
cur = cur.right
cur = stk.pop()
cur = cur.left
return res[::-1]
94. 二叉树的中序遍历¶
中序直接递归¶
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
left = self.inorderTraversal(root.left)
right = self.inorderTraversal(root.right)
return left + [root.val] + right
中序使用dfs递归¶
# 借助python函数传参特性
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def dfs(node, res):
if not node:
return
dfs(node.left, res)
res.append(node.val)
dfs(node.right, res)
res = []
dfs(root, res)
return res
# 利用nonlocal关键字
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def dfs(node):
nonlocal res
if not node:
return
dfs(node.left)
res.append(node.val)
dfs(node.right)
res = []
dfs(root)
return res
中序使用指针迭代¶
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
cur, stk, res = root, [], []
while cur or stk:
while cur:
stk.append(cur)
cur = cur.left
cur = stk.pop()
res.append(cur.val)
cur = cur.right
return res
102. 二叉树的层序遍历¶
层序递归¶
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
def bfs(node, level, levels):
if not node:
return
if len(levels) == level:
levels.append([])
levels[level].append(node.val)
bfs(node.left, level+1, levels)
bfs(node.right, level+1, levels)
res = []
bfs(root, 0, res)
return res
层序迭代¶
# 使用deque
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
que, res = deque([root]), []
while que:
len_que = len(que)
level = []
for _ in range(len_que):
cur = que.popleft()
level.append(cur.val)
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
res.append(level)
return res
# 使用列表
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
cur_level, res = [root], []
while cur_level:
level, level_val = [], []
for node in cur_level:
level_val.append(node.val)
if node.left:
level.append(node.left)
if node.right:
level.append(node.right)
cur_level = level
res.append(level_val)
return res
199.二叉树的右视图¶
题解：
- 显然层序遍历取每层最后一个节点即可
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
res, que = [], deque([root])
while que:
len_que = len(que)
for i in range(len(que)):
cur = que.popleft()
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
if i == len_que - 1:
res.append(cur.val)
return res
637.二叉树的层平均值¶
题解：
- 显然层序遍历求每层均值即可
class Solution:
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
res, que, = [], deque([root])
while que:
level = []
for _ in range(len(que)):
cur = que.popleft()
level.append(cur.val)
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
res.append(sum(level) / len(level))
return res
429. N叉树的层序遍历¶
题解：
- 类似于二叉树的层序遍历，只不过这里每个节点加入的是子节点，而二叉树分别加入左右节点
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
if not root:
return []
res, que = [], deque([root])
while que:
level = []
for _ in range(len(que)):
cur = que.popleft()
level.append(cur.val)
for child in cur.children:
que.append(child)
res.append(level)
return res
515. 在每个树行中找最大值¶
题解：
- 层序遍历并返回每一层的最大值
# 使用迭代
class Solution:
def largestValues(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
res, que = [], deque([root])
while que:
level = []
for _ in range(len(que)):
cur = que.popleft()
level.append(cur.val)
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
res.append(max(level))
return res
# 使用递归
class Solution:
def largestValues(self, root: Optional[TreeNode]) -> List[int]:
res = []
def bfs(root, h):
if root:
if h >= len(res):
res.append(root.val)
else:
res[h] = max(res[h], root.val)
bfs(root.left, h + 1)
bfs(root.right, h + 1)
bfs(root, 0)
return res
226. 翻转二叉树¶
题解：
- 递归解法
# 前序遍历
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
# 中序遍历
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
self.invertTree(root.left)
root.left, root.right = root.right, root.left
self.invertTree(root.left) # 这里需要注意仍然递归左子节点,因为左右节点已经互换了
return root
# 后序遍历
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
self.invertTree(root.left)
self.invertTree(root.right)
root.left, root.right = root.right, root.left
return root
dfs迭代解法：
# 前序遍历
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
stk = [root]
while stk:
node = stk.pop()
node.left, node.right = node.right, node.left
if node.left:
stk.append(node.left)
if node.right:
stk.append(node.right)
return root
# 中序遍历
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
stk = [root]
while stk:
node = stk.pop()
if node.left:
stk.append(node.left)
node.left, node.right = node.right, node.left
if node.left: # 这里需要注意仍然递归左子节点,因为左右节点已经互换了
stk.append(node.left)
return root
# 后序遍历
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
stk = [root]
while stk:
node = stk.pop()
if node.left:
stk.append(node.left)
if node.right:
stk.append(node.right)
node.left, node.right = node.right, node.left
return root
bfs迭代解法：
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
que = deque([root])
while que:
que_len = len(que)
for _ in range(que_len):
node = que.popleft()
node.left, node.right = node.right, node.left
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
return root
101. 对称二叉树¶
题解：
- 迭代法：本题首先想到可以使用层序遍历，判断每一层是否对称，需要注意的是空节点需要加入到列表中
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
que = deque([root])
while que:
len_que = len(que)
level = []
for _ in range(len_que):
cur = que.popleft()
if cur:
level.append(cur.val)
que.append(cur.left)
que.append(cur.right)
else:
level.append(None)
if level != level[::-1]:
return False
return True
- 迭代法：用队列/栈存储节点，然后按照左子树的左节点和右子树的右节点，左子树的右节点和右子树的左节点相互配对的顺序加入数据结构中，最后进行比较
# 使用队列
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
queue = collections.deque()
queue.append(root.left) #将左子树头结点加入队列
queue.append(root.right) #将右子树头结点加入队列
while queue: #接下来就要判断这这两个树是否相互翻转
leftNode = queue.popleft()
rightNode = queue.popleft()
if not leftNode and not rightNode: #左节点为空、右节点为空，此时说明是对称的
continue
#左右一个节点不为空，或者都不为空但数值不相同，返回false
if not leftNode or not rightNode or leftNode.val != rightNode.val:
return False
queue.append(leftNode.left) #加入左节点左孩子
queue.append(rightNode.right) #加入右节点右孩子
queue.append(leftNode.right) #加入左节点右孩子
queue.append(rightNode.left) #加入右节点左孩子
return True
# 使用栈
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
st = []
st.append(root.left)
st.append(root.right)
while st:
rightNode = st.pop()
leftNode = st.pop()
if not leftNode and not rightNode:
continue
if not leftNode or not rightNode or leftNode.val != rightNode.val:
return False
st.append(leftNode.left)
st.append(rightNode.right)
st.append(leftNode.right)
st.append(rightNode.left)
return True
- 递归法：
首先这里需要判断左右子树是否对称，那么要比较的是左子树的左节点和右子树的右节点，左子树的右节点和右子树的左节点
- 递归函数参数：左右子节点；返回值：布尔值
- 递归终止条件：分为5种情况，
- 左节点为空，右节点不为空，返回False
- 左节点不为空，右节点为空，返回False
- 左节点和右节点都为空，返回True
- 左节点的数值不等于右节点数值，返回False
- 最后一种情况就需要进入递归逻辑了
- 单层递归逻辑：比较左子树的左节点和右子树的右节点，左子树的右节点和右子树的左节点
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
def compare(left, right):
if not left and right:
return False
elif left and not right:
return False
elif not left and not right:
return True
elif left.val != right.val:
return False
return compare(left.left, right.right) and compare(left.right, right.left)
return compare(root.left, root.right)
104. 二叉树的最大深度¶
题解：
- 递归法：
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
l_depth = self.maxDepth(root.left)
r_depth = self.maxDepth(root.right)
return max(l_depth, r_depth) + 1
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
ans = 0
def dfs(node, cnt):
if node is None:
return
cnt += 1
nonlocal ans
ans = max(ans, cnt)
dfs(node.left, cnt)
dfs(node.right, cnt)
dfs(root, 0)
return ans
- 迭代法：层序遍历
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
que = deque([root])
res = 0
while que:
res += 1
len_que = len(que)
for _ in range(len_que):
node = que.popleft()
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
return res
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
# 层序遍历
res = 0
levels = []
def bfs(node, depth, levels):
if not node:
return
if len(levels) == depth:
levels.append([])
levels[depth].append(node.val)
bfs(node.left, depth + 1, levels)
bfs(node.right, depth + 1, levels)
bfs(root, 0, levels)
return len(levels)
559. N叉树的最大深度¶
题解：
- 递归法：
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def maxDepth(self, root: 'Node') -> int:
if not root:
return 0
depth = 1
for child in root.children:
depth = max(depth, self.maxDepth(child)+1)
return depth
- 迭代法：层序遍历
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def maxDepth(self, root: 'Node') -> int:
if not root:
return 0
que = deque([root])
depth = 0
while que:
depth += 1
len_que = len(que)
for _ in range(len_que):
node = que.popleft()
for child in node.children:
que.append(child)
return depth
111. 二叉树的最小深度¶
题解：
- 递归法：当左（右）子树为空的时候，最小深度是右（左）子树的最小深度而不是1
# 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 minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
if not root.left and root.right:
return 1 + self.minDepth(root.right)
elif root.left and not root.right:
return 1 + self.minDepth(root.left)
else:
return 1 + min(self.minDepth(root.left), self.minDepth(root.right))
- 迭代法：层序遍历，当节点的左右节点都为空时返回
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
que = deque([root])
res = 0
while que:
res += 1
len_que = len(que)
for _ in range(len_que):
node = que.popleft()
if not node.left and not node.right:
return res
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
return res
222. 完全二叉树的节点个数¶
题解：
- 层序遍历
# 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 countNodes(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
que = deque([root])
num = 0
while que:
len_que = len(que)
num += len_que
for _ in range(len_que):
node = que.popleft()
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
return num
- 递归法：
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return self.countNodes(root.left) + self.countNodes(root.right) + 1
- 利用完全二叉树的特性：完全二叉树要么是满二叉树，要么只有最后一层右侧存在空节点。==递归完全二叉树的左右节点，一定有其左子树或者右子树一定是满二叉树==。满二叉树节点数目可以用\(2^{depth}-1\)来求得。
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
count = 1
left, right = root.left, root.right
while left and right:
count += 1
left, right = left.left, right.right
if not left and not right:
return 2 ** count - 1
return self.countNodes(root.left) + self.countNodes(root.right) + 1
110. 平衡二叉树¶
题解：
-
递归：定义一个求二叉树深度的函数，当左右子树都是平衡二叉树并且它们之间的深度差小于等于1时返回True。此方法时间复杂度为\(O(nlogn)\)
-
时间复杂度：最差情况下（为 “满二叉树” 时），遍历树所有节点，判断每个节点的深度 depth(root) 需要遍历 各子树的所有节点 ，满二叉树高度的复杂度 O(logN)，将满二叉树按层分为 log(N+1) 层。通过调用 depth(root) ，判断二叉树各层的节点的对应子树的深度，需遍历节点数量为 \(N \times 1, \frac{N-1}{2} \times 2, \frac{N-3}{4} \times 4, \frac{N-7}{8} \times 8, ..., 1 \times \frac{N+1}{2}\), 因此各层执行 depth(root) 的时间复杂度为 O(N)
# 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 isBalanced(self, root: Optional[TreeNode]) -> bool:
def depth(node):
if not node:
return 0
return max(depth(node.left), depth(node.right)) + 1
if not root:
return True
return (abs(depth(root.left) - depth(root.right)) <= 1 and
self.isBalanced(root.left) and self.isBalanced(root.right))
- 递归：求二叉树深度的函数进一步简化，当二叉树不是平衡二叉树时返回-1。此方法时间复杂度为\(O(n)\)
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def recur(root):
if not root:
return 0
left = recur(root.left)
if left == -1:
return -1
right = recur(root.right)
if right == -1:
return -1
return max(left, right) + 1 if abs(left - right) <= 1 else -1
return recur(root) != -1
- 迭代法暂时不懂
257. 二叉树的所有路径¶
题解：
首先路径都是由根节点出发指向叶子节点，因此首先明确需要使用前序遍历（实际上'中左右'或者'中右左'都是可以的）。此外考虑到迭代法前序遍历每次检查一个根节点，如果维护一个路径的栈，就可以记录所有路径；如果采用递归法，每次到达叶子节点时需要把path回溯到父节点（这里有一个小技巧，如果采用字符串存储路径，因为字符串不可更改，path会创建新的临时字符串传参，这样就不用显示回溯了）
- 迭代解法：
# 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
stk, path_str, res = [root], [str(root.val)], []
while stk:
node = stk.pop()
path = path_str.pop()
if not node.left and not node.right:
res.append(path)
# 中左右
if node.right:
stk.append(node.right)
path_str.append(path+'->'+str(node.right.val))
if node.left:
stk.append(node.left)
path_str.append(path+'->'+str(node.left.val))
# 中右左
# if node.left:
# stk.append(node.left)
# path_str.append(path+'->'+str(node.left.val))
# if node.right:
# stk.append(node.right)
# path_str.append(path+'->'+str(node.right.val))
return res
- 递归解法：
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
def traversal(cur, path, result):
path.append(cur.val) # 中
if not cur.left and not cur.right: # 到达叶子节点
path_str = '->'.join(map(str, path))
result.append(path_str)
return
# 这里同样左右的顺序可以改变
if cur.right: # 右
traversal(cur.right, path, result)
path.pop() # 回溯
if cur.left: # 左
traversal(cur.left, path, result)
path.pop() # 回溯
result = []
path = []
if not root:
return result
traversal(root, path, result)
return result
# 用字符串记录路径
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
def traversal(cur: TreeNode, path: str, result: List[str]) -> None:
path += str(cur.val)
# 若当前节点为叶子节点，直接输出
if not cur.left and not cur.right:
result.append(path)
if cur.left:
# + '->' 是隐藏回溯
traversal(cur.left, path + '->', result)
if cur.right:
traversal(cur.right, path + '->', result)
path = ''
result = []
if not root: return result
traversal(root, path, result)
return result
404. 左叶子之和¶
题解：
-
首先需要明确左叶子节点的含义：父节点的左节点，且左节点的左右节点均为空；
-
迭代法：首先想到使用迭代解法，碰到左叶子节点记录就可以
# 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 sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
st = [root]
result = 0
while st:
node = st.pop()
if node.left and node.left.left is None and node.left.right is None:
result += node.left.val
if node.right:
st.append(node.right)
if node.left:
st.append(node.left)
return result
- 递归法：==递归的初衷应该是增加代码可读性！！==
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
self.res = 0
def dfs(node):
if not node:
return None
# 判断是否为左子节点，是否同时又是叶子节点
if node.left and not node.left.left and not node.left.right:
self.res += node.left.val #统计结果
dfs(node.left)
dfs(node.right)
dfs(root)
return self.res
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
res = 0
if root.left and not root.left.left and not root.left.right:
res += root.left.val
else:
res += self.sumOfLeftLeaves(root.left)
return res + self.sumOfLeftLeaves(root.right)
513. 找树左下角的值¶
题解：
- 首先想到层序遍历，返回层序遍历最后一层第一个值就可以
# 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 findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
que = deque([root])
res = []
while que:
len_que = len(que)
level = []
for _ in range(len_que):
node = que.popleft()
level.append(node.val)
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
res.append(level)
return res[-1][0]
- 递归法：递归法需要找到最深层的最左端叶子节点；所以首先需要找到最深层节点，然后需要先向左遍历；在寻找最深层节点时需要回溯，因为递归终止条件是找到叶子节点时返回
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
def traversal(node, depth):
if not node.left and not node.right:
if depth > self.max_depth:
self.max_depth = depth
self.result = node.val
return
if node.left: # 左
depth += 1
traversal(node.left, depth)
depth -= 1 # 回溯
# 上面三句也可以简化为
# traversal(node.left, depth+1)
if node.right: # 右
depth += 1
traversal(node.right, depth)
depth -= 1 # 回溯
# 上面三句也可以简化为
# traversal(node.right, depth+1)
self.max_depth = float('-inf')
self.result = None
traversal(root, 0)
return self.result
112. 路径总和¶
题解：
- 迭代法：本题可以按照二叉树的所有路径类似的处理方式，在用栈更新节点的同时更新路径和
# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
# 此时栈里要放的是pair<节点指针，路径数值>
st = [(root, root.val)]
while st:
node, path_sum = st.pop()
# 如果该节点是叶子节点了，同时该节点的路径数值等于sum，那么就返回true
if not node.left and not node.right and path_sum == targetSum:
return True
# 右节点，压进去一个节点的时候，将该节点的路径数值也记录下来
if node.right:
st.append((node.right, path_sum + node.right.val))
# 左节点，压进去一个节点的时候，将该节点的路径数值也记录下来
if node.left:
st.append((node.left, path_sum + node.left.val))
return False
- 递归法：简单递归代码很容易理解；常规递归思路是递归加回溯
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
if not root.left and not root.right and targetSum == root.val:
return True
return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
def traversal(cur: TreeNode, sum_rest: int) -> bool:
if not cur.left and not cur.right and sum_rest == 0: # 遇到叶子节点，并且计数为0
return True
if not cur.left and not cur.right: # 遇到叶子节点直接返回
return False
if cur.left: # 左
sum_rest -= cur.left.val
if traversal(cur.left, sum_rest): # 递归，处理节点
return True
sum_rest += cur.left.val # 回溯，撤销处理结果
# 以上4行可以简化为
# if traversal(cur.left, sum_rest - cur.left.val): # 递归，处理节点
# return True
if cur.right: # 右
sum_rest -= cur.right.val
if traversal(cur.right, sum_rest): # 递归，处理节点
return True
sum_rest += cur.right.val # 回溯，撤销处理结果
# 以上4行可以简化为
# if traversal(cur.left, sum_rest - cur.right.val): # 递归，处理节点
# return True
return False
if root is None:
return False
return traversal(root, targetSum - root.val)
106. 从后序与中序遍历序列构造二叉树¶
题解：
- 首先后序遍历最后一个元素为父节点，通过找到此父节点在中序遍历中的位置，即可找到父节点的左子树的元素的中序遍历即为此位置左边元素，同理父节点的右子树的元素的中序遍历为此位置右边元素；进一步地通过左右子树元素数目相同可以找到父节点的左右子树的后序遍历，接下来递归左右子树即可。==可以看出必须要借助中序遍历才能划分左右子树，如果利用前序和后序遍历则不能==
# 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, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
# 第一步: 特殊情况讨论: 树为空. (递归终止条件)
if not postorder:
return None
# 第二步: 后序遍历的最后一个就是当前的中间节点.
root_val = postorder[-1]
root = TreeNode(root_val)
# 第三步: 找切割点.
separator_idx = inorder.index(root_val)
# 第四步: 切割inorder数组. 得到inorder数组的左,右半边.
inorder_left = inorder[:separator_idx]
inorder_right = inorder[separator_idx + 1:]
# 第五步: 切割postorder数组. 得到postorder数组的左,右半边.
# ⭐️ 重点1: 中序数组大小一定跟后序数组大小是相同的.
postorder_left = postorder[:len(inorder_left)]
postorder_right = postorder[len(inorder_left): len(postorder) - 1]
# 第六步: 递归
root.left = self.buildTree(inorder_left, postorder_left)
root.right = self.buildTree(inorder_right, postorder_right)
# 第七步: 返回答案
return root
105. 从中序和前序遍历序列构造二叉树¶
题解：
- 解题思路和106. 从后序与中序遍历序列构造二叉树相同
# 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]:
if not preorder:
return
root_val = preorder[0]
root = TreeNode(root_val)
idx = inorder.index(root_val)
left_inorder = inorder[:idx]
right_inorder = inorder[idx+1:]
left_preorder = preorder[1:len(left_inorder)+1]
right_preorder = preorder[len(left_inorder)+1:]
root.left = self.buildTree(left_preorder, left_inorder)
root.right = self.buildTree(right_preorder, right_inorder)
return root
654. 最大二叉树¶
题解：
- 本题思路与105. 从中序和前序遍历序列构造二叉树以及106. 从后序与中序遍历序列构造二叉树思路相同
# 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 constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
if not nums:
return
root_val = max(nums)
root = TreeNode(root_val)
idx = nums.index(root_val)
left_nums = nums[:idx]
right_nums = nums[idx+1:]
root.left = self.constructMaximumBinaryTree(left_nums)
root.right = self.constructMaximumBinaryTree(right_nums)
return root
617. 合并二叉树¶
题解：
-
本题主要考察二叉树的遍历，可以采用递归也可以采用迭代
-
递归
# 递归：不构建新树
# 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 mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
# 递归终止条件:
# 但凡有一个节点为空, 就立刻返回另外一个. 如果另外一个也为None就直接返回None.
if not root1:
return root2
if not root2:
return root1
# 上面的递归终止条件保证了代码执行到这里root1, root2都非空.
root1.val += root2.val # 中
root1.left = self.mergeTrees(root1.left, root2.left) #左
root1.right = self.mergeTrees(root1.right, root2.right) # 右
return root1 # ⚠️ 注意: 本题我们重复使用了题目给出的节点而不是创建新节点. 节省时间, 空间.
# 递归：构建新树
class Solution:
def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
# 递归终止条件:
# 但凡有一个节点为空, 就立刻返回另外一个. 如果另外一个也为None就直接返回None.
if not root1:
return root2
if not root2:
return root1
# 上面的递归终止条件保证了代码执行到这里root1, root2都非空.
root = TreeNode() # 创建新节点
root.val += root1.val + root2.val# 中
root.left = self.mergeTrees(root1.left, root2.left) #左
root.right = self.mergeTrees(root1.right, root2.right) # 右
return root # ⚠️ 注意: 本题我们创建了新节点.
- 迭代：因为两颗树结构可能不一样，因此采用层次遍历
class Solution:
def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
if not root1:
return root2
if not root2:
return root1
queue = deque()
queue.append((root1, root2))
while queue:
node1, node2 = queue.popleft()
node1.val += node2.val
if node1.left and node2.left:
queue.append((node1.left, node2.left))
elif not node1.left:
node1.left = node2.left
if node1.right and node2.right:
queue.append((node1.right, node2.right))
elif not node1.right:
node1.right = node2.right
return root1
700. 二叉搜索树中的搜索¶
题解：
-
需要注意二叉搜索树的特征：左子树节点的元素均小于根节点的元素；右子树节点的元素均大于根节点的元素
-
递归法：
# 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 searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root or root.val == val:
return root
if root.val > val:
return self.searchBST(root.left, val)
if root.val < val:
return self.searchBST(root.right, val)
- 迭代法：
class Solution:
def searchBST(self, root: TreeNode, val: int) -> TreeNode:
while root:
if val < root.val:
root = root.left
elif val > root.val:
root = root.right
else:
return root
return None
98. 验证二叉搜索树¶
题解：
- ==二叉搜索树的中序遍历数组递增==，因此可以先用中序遍历得到遍历数组
# 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:
def inorder_traversal(root):
if not root:
return []
left = inorder_traversal(root.left)
right = inorder_traversal(root.right)
return left + [root.val] + right
vec = inorder_traversal(root)
for i in range(len(vec) - 1):
if vec[i] >= vec[i+1]:
return False
return True
# 迭代
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def inorder_traversal(root):
cur, stk, vec = root, [], []
while cur or stk:
while cur:
stk.append(cur)
cur = cur.left
cur = stk.pop()
vec.append(cur.val)
cur = cur.right
return vec
vec = inorder_traversal(root)
for i in range(len(vec) - 1):
if vec[i] >= vec[i+1]:
return False
return True
- 除了先求得中序遍历数组之外，也可以在中序遍历的过程中判断当前节点和前一个遍历的节点的大小。
# 迭代
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
cur, stk, pre = root, [], None
while cur or stk:
while cur:
stk.append(cur)
cur = cur.left
cur = stk.pop()
if pre and pre.val >= cur.val:
return False
pre = cur
cur = cur.right
return True
# 递归
class Solution:
def __init__(self):
self.pre = None # 用来记录前一个节点
def isValidBST(self, root):
if root is None:
return True
left = self.isValidBST(root.left)
if self.pre and self.pre.val >= root.val:
return False
self.pre = root # 记录前一个节点
right = self.isValidBST(root.right)
return left and right
530. 二叉搜索树的最小绝对差¶
题解：
- 本题与98. 验证二叉搜索树思路一致，都是利用二叉搜索树中序遍历的递增特性，因此仍然可以采用两种解法：第一种先得到中序遍历数组，然后再求最小绝对差；第二种则是直接在遍历过程中求解绝对差（此种解法需要注意前一个节点保存的技巧）
# 方法一
# 递归
# 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 getMinimumDifference(self, root: Optional[TreeNode]) -> int:
def inorder_traversal(root):
if not root:
return []
left = inorder_traversal(root.left)
right = inorder_traversal(root.right)
return left + [root.val] + right
res = inorder_traversal(root)
diff = float('inf')
for i in range(len(res) - 1):
diff_tmp = res[i+1] - res[i]
if diff_tmp < diff:
diff = diff_tmp
return diff
# 迭代
class Solution:
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
def inorder_traversal(root):
cur, stk, res = root, [], []
while cur or stk:
while cur:
stk.append(cur)
cur = cur.left
cur = stk.pop()
res.append(cur.val)
cur = cur.right
return res
res = inorder_traversal(root)
diff_min = float('inf')
for i in range(len(res) - 1):
diff = res[i + 1] - res[i]
if diff_min > diff:
diff_min = diff
return diff_min
# 方法二
# 递归
class Solution:
def __init__(self):
self.diff_min = float('inf')
self.pre = None
def inorder_traversal(self, root):
if not root:
return
left = self.inorder_traversal(root.left)
if self.pre and self.diff_min > root.val - self.pre.val:
self.diff_min = root.val - self.pre.val
self.pre = root
right = self.inorder_traversal(root.right)
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
self.inorder_traversal(root)
return self.diff_min
# 迭代
class Solution:
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
cur, stk, pre, diff_min = root, [], None, float('inf')
while cur or stk:
while cur:
stk.append(cur)
cur = cur.left
cur = stk.pop()
if pre:
diff = cur.val - pre.val
if diff_min > diff:
diff_min = diff
pre = cur
cur = cur.right
return diff_min
501. 二叉搜索树中的众数¶
题解：
-
首先考虑如果是普通二叉树应该怎么找出众数呢？最直观的做法是遍历过程（这里遍历可以是任意一种方式）中把每个节点的值存入一个哈希表中，然后取出哈希表的最高频元素；
-
对于二叉搜索树，因为中序遍历单调性，==因此可以在遍历的同时就可以求出节点元素出现的频率==，由于众数可能不止一个，因此常规做法是先把频率统计出来，然后再遍历一遍，这样相当于时间复杂度提升一倍；这里有一个只需要遍历一遍的巧妙方式，在遍历过程中记录当前最大频率的元素，一旦发现一个更高频率的数就清除目前的结果。
-
方法一：先遍历得到频率哈希表
# 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
# 先得到遍历数组，然后再求频率哈希表（利用Counter）
class Solution:
def findMode(self, root: Optional[TreeNode]) -> List[int]:
def inorder_traversal(root):
if not root:
return []
left = inorder_traversal(root.left)
right = inorder_traversal(root.right)
return left + [root.val] + right
res = inorder_traversal(root)
res_cnt = Counter(res)
freq_max = max(res_cnt.values())
ans = []
for k, v in res_cnt.items():
if v == freq_max:
ans.append(k)
return ans
# 遍历过程中得到频率哈希表（利用defaultdict）
class Solution:
def searchBST(self, cur, freq_map):
if cur is None:
return
freq_map[cur.val] += 1 # 统计元素频率
self.searchBST(cur.left, freq_map)
self.searchBST(cur.right, freq_map)
def findMode(self, root):
freq_map = defaultdict(int) # key:元素，value:出现频率
result = []
if root is None:
return result
self.searchBST(root, freq_map)
max_freq = max(freq_map.values())
for key, freq in freq_map.items():
if freq == max_freq:
result.append(key)
return result
- 方法二：一次遍历得到结果
# 迭代法
class Solution:
def findMode(self, root: Optional[TreeNode]) -> List[int]:
st = []
cur = root
pre = None
maxCount = 0 # 最大频率
count = 0 # 统计频率
result = []
while cur is not None or st:
if cur is not None: # 指针来访问节点，访问到最底层
st.append(cur) # 将访问的节点放进栈
cur = cur.left # 左
else:
cur = st.pop()
if pre is None: # 第一个节点
count = 1
elif pre.val == cur.val: # 与前一个节点数值相同
count += 1
else: # 与前一个节点数值不同
count = 1
if count == maxCount: # 如果和最大值相同，放进result中
result.append(cur.val)
if count > maxCount: # 如果计数大于最大值频率
maxCount = count # 更新最大频率
result = [cur.val] # 很关键的一步，不要忘记清空result，之前result里的元素都失效了
pre = cur
cur = cur.right # 右
return result
# 递归法
class Solution:
def __init__(self):
self.maxCount = 0 # 最大频率
self.count = 0 # 统计频率
self.pre = None
self.result = []
def searchBST(self, cur):
if cur is None:
return
self.searchBST(cur.left) # 左
# 中
if self.pre is None: # 第一个节点
self.count = 1
elif self.pre.val == cur.val: # 与前一个节点数值相同
self.count += 1
else: # 与前一个节点数值不同
self.count = 1
self.pre = cur # 更新上一个节点
if self.count == self.maxCount: # 如果与最大值频率相同，放进result中
self.result.append(cur.val)
if self.count > self.maxCount: # 如果计数大于最大值频率
self.maxCount = self.count # 更新最大频率
self.result = [cur.val] # 很关键的一步，不要忘记清空result，之前result里的元素都失效了
self.searchBST(cur.right) # 右
return
def findMode(self, root):
self.count = 0
self.maxCount = 0
self.pre = None # 记录前一个节点
self.result = []
self.searchBST(root)
return self.result
236. 二叉树的最近公共祖先¶
题解：
-
经过分析可知：若 root 是 p,q的 最近公共祖先 ，则只可能为以下情况之一：
-
p和 q在 root 的子树中，且分列 root的 异侧（即分别在左、右子树中）；
- p=root，且 q在 root 的左或右子树中；
-
q=root，且 p在 root的左或右子树中；
-
本题是考察对递归理解的好题
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root == p or root == q or not root:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
elif left and not right:
return left
elif not left and right:
return right
else:
return None
235. 二叉搜索树的最近公共祖先¶
题解：
- 本题相比236. 二叉树的最近公共祖先多了二叉搜索树这个限制条件，因此多了一个有序性的条件。二叉搜索树的两个节点的最近公共祖先一定位于这两个节点数值中间，并且在遍历过程中==第一个==遇到的满足条件的节点即为最近公共祖先。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# 递归
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root.val > p.val and root.val > q.val:
return self.lowestCommonAncestor(root.left, p, q)
elif root.val < p.val and root.val < q.val:
return self.lowestCommonAncestor(root.right, p, q)
else:
return root
# 迭代
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while root:
if root.val > p.val and root.val > q.val:
root = root.left
elif root.val < p.val and root.val < q.val:
root = root.right
else:
return root
return None
701. 二叉搜索树中的插入操作¶
题解：
- 尽管存在多种重构的二叉搜索树满足条件，但是只用二叉搜索树的逻辑构建即可。即：==插入节点原本位置为空==，且其大小与其父节点满足二叉搜索树的大小关系（二叉搜索树添加节点只需要在叶子上添加就可以）。
# 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 insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root:
node = TreeNode(val)
return node
if root.val > val:
root.left = self.insertIntoBST(root.left, val)
elif root.val < val:
root.right = self.insertIntoBST(root.right, val)
return root
# 迭代法
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root:
return TreeNode(val)
parent = None
cur = root
while cur:
parent = cur
if val < cur.val:
cur = cur.left
else:
cur = cur.right
if val < parent.val:
parent.left = TreeNode(val)
else:
parent.right = TreeNode(val)
return root