二叉树的算法

112. 路径总和

力扣题目链接(opens new window)

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例: 给定如下二叉树，以及目标和 sum = 22，

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2

class Solution:def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:if not root:return FalsetargetSum = targetSum - root.valif  (not root.left) and  (not root.right) and targetSum == 0:return True return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right,targetSum)

513.找树左下角的值

力扣题目链接(opens new window)

给定一个二叉树，在树的最后一行找到最左边的值。

示例 1:

示例 2:

def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:if not root: return -1queue=[]queue.append(root)results = []while queue:level = len(queue)result = []for _ in range(level):node = queue.pop(0)result.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)results.append(result)return results[-1][0]

def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:if not postorder:return NonerootVal = postorder[-1]root = TreeNode(rootVal)i = inorder.index(rootVal)left_inorder = inorder[:i]right_inorder = inorder[i + 1:]left_postorder = postorder[:len(left_inorder)]right_postorder = postorder[len(left_inorder): len(postorder) - 1]root.left = self.buildTree(left_inorder, left_postorder)root.right = self.buildTree(right_inorder, right_postorder)return root

def buildTreeWithPreAndIn(self,preorder:List[int], inorder:List[int]):if not preorder:return NonerootVal = preorder[0]root = TreeNode(rootVal)i = preorder.index(rootVal)left_inorder = inorder[:i - 1]right_inorder = inorder[i:]left_preorder = preorder[1:1 + len(left_inorder)]right_preorder = preorder[1 + len(left_inorder):]root.left = self.buildTreeWithPreAndIn(left_preorder,left_inorder)root.right = self.buildTreeWithPreAndIn(right_preorder,right_inorder)return root

1. python 中的 &&  | 用 and  和or 表示

2. 判空  if root   if not root   

queue = []

3. 方法内部调用自己要用self

4.判空 if not  list 

   list[-1] 取最后一个元素

   list[:1] 包含1

   list[1:] 不包含1

   list[1:2] 包含1 不包含1