513. 找树左下角的值 - 力扣（LeetCode）

image.png

两种方法，层序遍历和递归

# 递归，没有中，只有左右
# 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 findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        
        self.maxdepth = float('-inf')
        self.result = None
        self.find_bleft(root, 0)
        return self.result

    def find_bleft(self, cur, depth):
        if cur.left == None and cur.right == None:
            if depth > self.maxdepth:
                self.maxdepth = depth
                self.result = cur.val

                return self.result

        if cur.left:
            depth += 1
            self.find_bleft(cur.left, depth)
            depth -= 1

        if cur.right:
            depth += 1
            self.find_bleft(cur.right, depth)
            depth -= 1        

# 层序遍历
# 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
from collections import deque
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        if not root:
            return

        result = None
        que = deque()
        que.append(root)

        while que:
            n = len(que)

            for i in range(n):
                cur = que.popleft()
                if i == 0:
                    result = cur.val
                if cur.left:
                    que.append(cur.left)

                if cur.right:
                    que.append(cur.right)

        return result

112. 路径总和 - 力扣（LeetCode）

image.png

# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        return self.traversal(root,targetSum-root.val)

    def traversal(self, cur, targetSum):
        if cur.left == None and cur.right == None and targetSum == 0:
            return True
        if cur.left == None and cur.right == None and targetSum != 0:
            return False

        if cur.left:
            targetSum -= cur.left.val
            if self.traversal(cur.left, targetSum):
                return True
            targetSum += cur.left.val

        if cur.right:
            targetSum -= cur.right.val
            if self.traversal(cur.right, targetSum):
                return True
            targetSum += cur.right.val

        return False    

106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

image.png

• 注意套路

# 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]) -> Optional[TreeNode]:
        # 1、排除特殊情况
        if not postorder: 
            return None

        # 2、同一个后序遍历区间的最后一个元素是当前二叉树的root
        root_val = postorder[-1]
        root  = TreeNode(root_val)

        # 3、找中序切割点：之前root的中序index
        sep_idx = inorder.index(root_val)

        # 4、切割inorder数组，得到其左右半边
        inorder_left = inorder[:sep_idx]
        inorder_right = inorder[sep_idx + 1:]

        # 5、切割postorder，
        # 注意 中序的左右区间大小一定是和后序左右区间大小一样的
        postorder_left = postorder[:len(inorder_left)]
        postorder_right = postorder[len(inorder_left) : len(postorder) - 1]

        # 6、递归
        root.left = self.buildTree(inorder_left, postorder_left)
        root.right = self.buildTree(inorder_right, postorder_right)

        # 7、返回结果
        return root