题目简介
513: 找树左下角的值
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
112: 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
113: 路径总和ii
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
106: 从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
105: 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
初见思路
513.最直观的方法就是层序遍历来找
from collections import deque
class Solution:
def findBottomLeftValue(self, root):
if root is None:
return 0
queue = deque()
queue.append(root)
result = 0
while queue:
size = len(queue)
for i in range(size):
node = queue.popleft()
if i == 0:
result = node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
112 & 113 可以借鉴之前回溯的逻辑, 113的进阶就是在原来基础上把路径记录下来
## 112
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
self.nodes = [root.val]
return self.traversal(root, targetSum)
def traversal(self,node,targetSum):
if not node.left and not node.right:
# print(self.nodes)
if sum(self.nodes) == targetSum:
return True
left_ans, right_ans = False,False
if node.left:
self.nodes.append(node.left.val)
left_ans = self.traversal(node.left, targetSum)
self.nodes.pop()
if node.right:
self.nodes.append(node.right.val)
right_ans = self.traversal(node.right, targetSum)
self.nodes.pop()
return left_ans or right_ans
## 113
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
if not root:
return list()
self.path = list()
self.nodes = [root.val]
self.traversal(root, targetSum)
return self.path
def traversal(self,node,targetSum):
if not node.left and not node.right:
# print(self.nodes)
if sum(self.nodes) == targetSum:
self.path.append(list(self.nodes))
if node.left:
self.nodes.append(node.left.val)
self.traversal(node.left, targetSum)
self.nodes.pop()
if node.right:
self.nodes.append(node.right.val)
self.traversal(node.right, targetSum)
self.nodes.pop()
105 & 106: 这道题重点是考察前中后序的规律。两道变式题区别只是在于，前序遍历从前到后，后序遍历从后到前。
## 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)
separate_idx = inorder.index(root_val)
inorder_left = inorder[:separate_idx]
inorder_right = inorder[separate_idx+1:]
preorder_left = preorder[1:1+len(inorder_left)]
preorder_right = preorder[1+len(inorder_left):]
root.left = self.buildTree(preorder_left, inorder_left)
root.right = self.buildTree(preorder_right, inorder_right)
return root
## 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)
separate_idx = inorder.index(root_val)
separate_left = inorder[:separate_idx]
separate_right = inorder[separate_idx+1:]
postorder_left = postorder[:len(separate_left)]
postorder_right = postorder[len(separate_left):-1]
root.left = self.buildTree(separate_left, postorder_left)
root.right = self.buildTree(separate_right, postorder_right)
return root
复盘思路
513有性能上更快的递归回溯法:
class Solution:
def findBottomLeftValue(self, root):
self.max_depth = float('-inf')
self.result = None
self.traversal(root, 0)
return self.result
def traversal(self, 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:
self.traversal(node.left, depth+1)
if node.right:
self.traversal(node.right, depth+1)
112 看了自己以前Java的终极简洁递归
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
if not root.left and not root.right:
return root.val == targetSum
return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)
重点难点
https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html
https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html
