代码随想录算法训练营 Day 14
Published:
Q1. LeetCode 513
思路 - 任何遍历方式都可以
保证了左子树优先遍历。注意需要找到的是最后一层的最左边节点
解法1. 递归+回溯
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
def dfs(node, depth):
# 找到叶子节点
if not node.left and not node.right:
# 更新外部定义的变量，需要用到nonlocal关键字
nonlocal max_depth, res
if depth > max_depth:
max_depth = depth
res = node.val
return
if node.left:
dfs(node.left, depth + 1)
if node.right:
dfs(node.right, depth + 1)
max_depth = float('-inf')
res = 0
dfs(root, 0)
return res
解法2: 迭代法
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
res = 0
queue = deque([root])
while queue:
for i in range(len(queue)):
curr = queue.popleft()
# 层序遍历，最先推出的就是这一层最左边的节点
if i == 0:
res = curr.val
if curr.left:
queue.append(curr.left)
if curr.right:
queue.append(curr.right)
return res
Take some notes
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。（通常使用前序遍历）
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。（通常使用后序遍历）
Q2. LeetCode 112
思路 - 任何遍历方式都可以
解法1: 递归法
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
def dfs(node, s):
if not node.left and not node.right:
if s + node.val == targetSum:
return True
else:
return False
if node.left:
if dfs(node.left, s + node.val):
return True
if node.right:
if dfs(node.right, s + node.val):
return True
return False
return dfs(root, 0)
解法2: 迭代法
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
stack = [(root, 0)]
while stack:
curr, s = stack.pop()
if not curr.left and not curr.right:
if s + curr.val == targetSum:
return True
if curr.right:
stack.append((curr.right, s + curr.val))
if curr.left:
stack.append((curr.left, s + curr.val))
return False
Q3. LeetCode 113
思路 - 任何遍历方式都可以
解法1: 递归法
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
if not root:
return []
res = []
path = []
def dfs(node, s):
if not node.left and not node.right:
path.append(node.val)
if s + node.val == targetSum:
res.append(path[:])
path.pop()
return
if node.left:
path.append(node.val)
dfs(node.left, s + node.val)
path.pop()
if node.right:
path.append(node.val)
dfs(node.right, s + node.val)
path.pop()
return
dfs(root, 0)
return res
解法2: 迭代法
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
if not root:
return []
res = []
stack = [(root, 0, [])]
while stack:
curr, s, path = stack.pop()
if not curr.left and not curr.right:
path.append(curr.val)
if s + curr.val == targetSum:
res.append(path[:])
# path.pop()
if curr.right:
stack.append((curr.right, s + curr.val, path + [curr.val]))
if curr.left:
stack.append((curr.left, s + curr.val, path + [curr.val]))
return res
Q4. LeetCode 106
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_left = inorder[:separator_idx]
inorder_right = inorder[separator_idx + 1:]
# 左右子树的遍历结果长度应该保持一致
postorder_left = postorder[:len(inorder_left)]
postorder_right = postorder[len(inorder_left):-1]
root.left = self.buildTree(inorder_left, postorder_left)
root.right = self.buildTree(inorder_right, postorder_right)
return root
Q5. LeetCode 105
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
separator_idx = inorder.index(root_val)
inorder_left = inorder[:separator_idx]
inorder_right = inorder[separator_idx + 1:]
preorder_left = preorder[1:len(inorder_left) + 1]
preorder_right = preorder[len(inorder_left) + 1:]
root.left = self.buildTree(preorder_left, inorder_left)
root.right = self.buildTree(preorder_right, inorder_right)
return root
总结
- 递归函数是否需要返回值：1). 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。2). 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。3). 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）
- 前序和中序可以确定唯一二叉树，中序和后序也可以确定唯一二叉树，但前序和后序无法确定