day16-binary tree-part04-7.18

tasks for today

1. 513 找树左下角值

2. 112路径总和

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

-------------------------------------------------------------------------------

1. 513 找树左下角值

This practice is suitable for the BFS (layer traverse), record each layer's value and return the last layer's first value

# 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:
        result = []
        nodeQueue = collections.deque([root])
        while nodeQueue:
            level = []
            for _ in range(len(nodeQueue)):
                cur = nodeQueue.popleft()
                level.append(cur.val)
                if cur.left:
                    nodeQueue.append(cur.left)
                if cur.right:
                    nodeQueue.append(cur.right)
            result.append(level)
        
        return result[-1][0]

本题如果使用dfs，前序遍历需要进行回溯

本题若使用递归法需要注意的是中止条件部分需要进行修改，除了正常的中止，要记得是否需要更新深度，以及更新result值，这个result值是外界的，不会参与每个点的递归

class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
        self.max_depth = float('-inf')
        self.result = None
        self.traversal(root, 0)
        return self.result
    
    def traversal(self, node, depth):
        if not node.left and not node.right:
            if depth > self.max_depth:
                self.max_depth = depth
                self.result = node.val
            return
        
        if node.left:
            depth += 1
            self.traversal(node.left, depth)
            depth -= 1
        if node.right:
            depth += 1
            self.traversal(node.right, depth)
            depth -= 1

2. 112路径总和

本题采用迭代法，BFS广度优先搜索，最合适，并且本题蕾丝与另一道找到所有二叉树路径的题目；基本思路就是再定义一个deque来记录pathsum的push过程，然后用一个result来存储结果

# 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:
            if root.val == targetSum: return True
            else: return False
        nodeQueue = collections.deque([root])
        pathQueue = collections.deque([0])
        result = []
        while nodeQueue:
            cur = nodeQueue.popleft()
            pathsum = pathQueue.popleft() + cur.val
            if cur.left:
                nodeQueue.append(cur.left)
                pathQueue.append(pathsum)
            if cur.right:
                nodeQueue.append(cur.right)
                pathQueue.append(pathsum)
            if cur.left is None and cur.right is None:
                result.append(pathsum)
        
        if targetSum in result: return True
        else: return False

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

pending, because my laptop is sent to get repaired, get in some water