求职刷题 力扣 day18 ---二叉树 part05

513. 找树左下角的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

思路：

层序遍历，每层的i == 0 的节点的值赋值给res，最后res一定是最后一层最左侧的节点的值

代码实现

from collections import deque
# 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:
        #层序遍历
        if not root: return 
        queue = deque()
        queue.append(root)

        while queue:
            for i in range(len(queue)):
                root = queue.popleft()
                if i == 0:
                    res = root.val
                if root.left:
                    queue.append(root.left)
                if root.right:
                    queue.append(root.right)
        return res

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

思路：

前序遍历，叶子节点的时候判断当前的求和是否等于targetValue，如果相等return True

代码实现

# 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:
        #前序遍历，终止到叶子节点
        def recur(root: Optional[TreeNode], sum_val: int) -> bool:
            if not root: return False
            sum_val += root.val
            if not root.left and not root.right:
                return True if sum_val == targetSum else False
            return recur(root.left, sum_val) or recur(root.right, sum_val)
        return recur(root, 0)

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

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

思路

思路：

后序遍历的结果确定根节点的值，然后确定中序遍历中根节点的位置，从而确定左子树和右子树的元素的长度，以及对应的中序遍历、后序遍历的结果，从而进行递归

代码实现

# Definition for a binary tree node.
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        # 左根右、 左右根
        # 思路，根据后序遍历确定根节点，然后在中序遍历中找到对应的根节点，然后确定左子树节点和右子树的节点
        # buildTree函数返回的是根据inorder 和 postorder 重构的树
        # 终止条件，inorder和postorder为空的时候返回None

        # 根据inorder构建value_index的dict可以有效的减少时间复杂度
        inorder_value_index_dict = {value: index for index, value in enumerate(inorder)}
        if not len(inorder):
            return None
        # 确定根节点的值
        def getTree(inorder_left: int, inorder_right: int, postorder_left: int, postorder_right: int) -> TreeNode:
            if inorder_left >= inorder_right:
                return
            root_val = postorder[postorder_right - 1]
            #确定中序遍历中根节点的位置
            root_index = inorder_value_index_dict[root_val]
            #构建树
            root = TreeNode(root_val)
            root.left = getTree(inorder_left, root_index, postorder_left, postorder_left + root_index - inorder_left)
            root.right = getTree(root_index + 1, inorder_right, postorder_left + root_index - inorder_left, postorder_right - 1)
            return root
        root = getTree(0, len(inorder), 0, len(postorder))
        return root