18天【代码随想录算法训练营34期】● 513.找树左下角的值 ● 112. 路径总和 113.路径总和ii ● 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树

513.找树左下角的值

# 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:
        q_ = []
        result = []
        if root:
            q_.append(root)
        while q_:
            lyr = []
            for i in range(len(q_)):
                temp = q_.pop(0)
                lyr.append(temp)
                if temp.left:
                    q_.append(temp.left)
                if temp.right:
                    q_.append(temp.right)
            result.append(lyr)
        return result[-1][0].val

# 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.result = None
        self.max_depth = float('-inf')
        self.traversal(root, 0)
        return self.result
    def traversal(self, node, depth):
        if node.left is None and node.right is None:
            if depth > self.max_depth:
                self.max_depth = depth
                self.result = node.val
            return
        else:
            if node.left:
                self.traversal(node.left, depth+1)
            if node.right:
                self.traversal(node.right, depth+1)

112. 路径总和

# 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 root is None:
            return False
        if root.left is None and root.right is None and root.val == targetSum:
            return True
        else:
            leftSum = self.hasPathSum(root.left, targetSum - root.val)
            rightSum = self.hasPathSum(root.right, targetSum - root.val)
            return leftSum or rightSum

113.路径总和ii

106.从中序与后序遍历序列构造二叉树

105.从前序与中序遍历序列构造二叉树