2022-12-25Day17 Day18

Day17

110.平衡二叉树

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        height_map ={}
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                stack.append(node)
                stack.append(None)
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
            else:
                real_node= stack.pop()
                left,right = height_map.get(real_node.left,0),height_map.get(real_node.right,0)
                if abs(left-right)>1:
                    return False
                height_map[real_node] = 1+max(left,right)
        return True 

257. 二叉树的所有路径

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        if not root:
            return []
        stack,res,stackpath = [root],[],[]
        stackpath.append(str(root.val))
        while stack:
            #节点和路径出栈
            node= stack.pop()
            path = stackpath.pop()
            #如果当前节点为叶子节点
            if node.left == None and node.right == None:
                res.append(path)
            #右子树入栈
            if node.right:
                stack.append(node.right)
                stackpath.append(path+'->'+str(node.right.val))
            #左子树入栈
            if node.left:
                stack.append(node.left)
                stackpath.append(path +'->'+str(node.left.val))
        return res 

404. 左叶子之和

class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0 
        stack = [root]
        res = 0
        while stack:
            node = stack.pop()
            if node.left  and not node.left.left  and not  node.left.right:
                res += node.left.val 
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return res 

Day18

513.找树左下角的值

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 
        stack = deque([root])
        res = 0 
        while stack:
            n = len(stack)
            res = stack[0].val 
            for _ in range(n):
                node = stack.popleft()
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
        return res 

112. 路径总和

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        que = collections.deque()
        que.append((root, root.val))
        while que:
            node, path = que.popleft()
            if not node.left and not node.right and path == targetSum:
                return True
            if node.left:
                que.append((node.left, path + node.left.val))
            if node.right:
                que.append((node.right, path + node.right.val))
        return False

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

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not postorder:
            return None
        #第一步 后序遍历的最后一个节点就是根节点
        root_val = postorder[-1] 
        root = TreeNode(root_val)
        #第二步 找切割点
        separet_idx = inorder.index(root_val)

        #第三步 切割inorder数组，
        inorder_left = inorder[:separet_idx]
        inorder_right = inorder[separet_idx+1:]

        #第四步 切割postorder数组
        postorder_left = postorder[:len(inorder_left)]
        postorder_right = postorder[len(inorder_left):len(postorder)-1]
        #第五步 递归
        root.left = self.buildTree(inorder_left,postorder_left)
        root.right = self.buildTree(inorder_right,postorder_right)

        return root