513.找树左下角的值
深度优先搜索
class Solution: def findBottomLeftValue(self, root: Optional[TreeNode]) -> int: curVal = curHeight = 0 def dfs(node: Optional[TreeNode], height: int) -> None: if node is None: return height += 1 dfs(node.left, height) dfs(node.right, height) nonlocal curVal, curHeight if height > curHeight: curHeight = height curVal = node.val dfs(root, 0) return curVal
广度优先搜索
class Solution: def findBottomLeftValue(self, root: Optional[TreeNode]) -> int: q = deque([root]) while q: node = q.popleft() if node.right: q.append(node.right) if node.left: q.append(node.left) ans = node.val return ans
112. 路径总和
广度优先搜索
class Solution: def hasPathSum(self, root: TreeNode, sum: int) -> bool: if not root: return False que_node = collections.deque([root]) que_val = collections.deque([root.val]) while que_node: now = que_node.popleft() temp = que_val.popleft() if not now.left and not now.right: if temp == sum: return True continue if now.left: que_node.append(now.left) que_val.append(now.left.val + temp) if now.right: que_node.append(now.right) que_val.append(now.right.val + temp) return False
113. 路经总和II
广度优先搜索
class Solution: def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]: ret = list() path = list() def dfs(root: TreeNode, targetSum: int): if not root: return path.append(root.val) targetSum -= root.val if not root.left and not root.right and targetSum == 0: ret.append(path[:]) dfs(root.left, targetSum) dfs(root.right, targetSum) path.pop() dfs(root, targetSum) return ret
105. 从前序与中序遍历序列构造二叉树
递归
class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: def myBuildTree(preorder_left: int, preorder_right: int, inorder_left: int, inorder_right: int): if preorder_left > preorder_right: return None # 前序遍历中的第一个节点就是根节点 preorder_root = preorder_left # 在中序遍历中定位根节点 inorder_root = index[preorder[preorder_root]] # 先把根节点建立出来 root = TreeNode(preorder[preorder_root]) # 得到左子树中的节点数目 size_left_subtree = inorder_root - inorder_left # 递归地构造左子树，并连接到根节点 # 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素 root.left = myBuildTree(preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1) # 递归地构造右子树，并连接到根节点 # 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素 root.right = myBuildTree(preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right) return root n = len(preorder) # 构造哈希映射，帮助我们快速定位根节点 index = {element: i for i, element in enumerate(inorder)} return myBuildTree(0, n - 1, 0, n - 1)
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]) -> TreeNode: # 递归中止条件：树为空 if not inorder or not postorder: return None # 根节点的值为后序遍历的最后一个元素值 rootVal = postorder[-1] # 创建根节点 root = TreeNode(rootVal) # 用根节点的值去中序数组中查找对应元素下标 midIndex = inorder.index(rootVal) # 找出中序遍历的左子树和右子树 # 左子树区间为 [0,midIndex),右子树区间为[midIndex+1，n-1] inorderLeft = inorder[:midIndex] inorderRight = inorder[midIndex + 1:] # 找出后序遍历的左子树和右子树 # 后序遍历和中序遍历的左子树和右子树长度相等，所以可以通过中序遍历左右子树的长度来确定后序遍历左右子树的位置 postorderLeft = postorder[: len(inorderLeft)] postorderRight = postorder[len(inorderLeft): len(inorder) - 1] # 递归遍历左子树 root.left = self.buildTree(inorderLeft, postorderLeft) # 递归遍历右子树 root.right = self.buildTree(inorderRight, postorderRight) return root