513.找树左下角的值
1、层序遍历迭代法
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
queue = [root]
res = float('-inf')
while queue:
n = len(queue)
for i in range(n):
node = queue.pop(0)
if i == 0:
res = node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return res
2、递归回溯法
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
self.max_depth = float("-inf")
self.res = None
self.dfs(root, 0)
return self.res
def dfs(self, root, depth):
if not root.left and not root.right:
if depth > self.max_depth:
self.max_depth = depth
self.res = root.val
return
if root.left:
depth += 1
self.dfs(root.left, depth)
depth -= 1
if root.right:
depth += 1
self.dfs(root.right, depth)
depth -= 1
112. 路径总和1
1、递归回溯法
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if root is None:
return False
if root.left is None and root.right is None and root.val == targetSum:
return True
left = self.hasPathSum(root.left, targetSum - root.val)
right = self.hasPathSum(root.right, targetSum - root.val)
return left or right
2、递归回溯精简版
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if root is None:
return False
return self.dfs(root, targetSum - root.val)
def dfs(self, node, count):
if node.left is None and node.right is None and count == 0:
return True
if node.left is None and node.right is None:
return False
if node.left:
count -= node.left.val
if self.dfs(node.left, count):
return True
count += node.left.val
if node.right:
count -= node.right.val
if self.dfs(node.right, count):
return True
count += node.right.val
return False
3、迭代法
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if root is None:
return False
stack = [(root, root.val)]
while stack:
node, node_sum = stack.pop()
if not node.left and not node.right and node_sum == targetSum:
return True
if node.right:
stack.append((node.right, node_sum + node.right.val))
if node.left:
stack.append((node.left, node_sum + node.left.val))
return False
0113.路径总和-ii
1、递归回溯
class Solution:
def __init__(self):
self.path = []
self.res = []
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
self.path.clear()
self.res.clear()
if root is None:
return self.res
self.path.append(root.val)
self.dfs(root, targetSum - root.val, self.path, self.res)
return self.res
def dfs(self, node, count, path, res):
if node.left is None and node.right is None and count == 0:
res.append(self.path[:])
return
if node.left is None and node.right is None and count != 0:
return
if node.left:
self.path.append(node.left.val)
count -= node.left.val
self.dfs(node.left, count, self.path, self.res)
# 回溯
count += node.left.val
self.path.pop()
if node.right:
self.path.append(node.right.val)
count -= node.right.val
self.dfs(node.right, count, self.path, self.res)
# 回溯
count += node.right.val
self.path.pop()
return
2、精简版，直接回溯一个节点
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
path = []
res = []
self.dfs(root, targetSum, path, res)
return res
def dfs(self, node, count, path, res):
# 退出条件
if node is None:
return
path.append(node.val)
count -= node.val
if node.left is None and node.right is None and count == 0:
res.append(path[:])
self.dfs(node.left, count, path, res)
self.dfs(node.right, count, path, res)
# 节点回溯
path.pop()
3、迭代法
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
res = []
if root is None:
return res
stack = [(root, [root.val])]
while stack:
node, path = stack.pop()
if node.left is None and node.right is None and sum(path) == targetSum:
res.append(path)
if node.right:
stack.append((node.right, path + [node.right.val]))
if node.left:
stack.append((node.left, path + [node.left.val]))
return res
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
if len(postorder) == 0:
return None
# 根节点
root_val = postorder[-1]
root = TreeNode(root_val)
# 找切割点
index = inorder.index(root_val)
# 切割中序数组
inorder_left = inorder[:index]
inorder_right = inorder[index+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