【基础算法精讲-学习记录】二叉树1

视频学习记录

https://www.bilibili.com/video/BV1UD4y1Y769/

• 二叉树往往用递归的方法比较好解决，而思考如何递归的秘诀在于：从顶层视角看，对于一个节点，上面递什么，下面归什么，边界条件是什么。

• 换句话就是，不要被整体迷住，专注于其中的一个节点和其左右子树的关系（有时还有父节点传的东西）就行

例题和课后作业代码记录

104. 二叉树的最大深度

https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/

# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        # 时间：遍历所有节点 On
        # 空间：最坏情况下，节点都在单边，On
        if not root:
            return 0 
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

111. 二叉树的最小深度

https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/

# 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 minDepth(self, root: Optional[TreeNode]) -> int:
        # 时间：遍历所有节点 On
        # 空间：最坏情况下，节点都在单边，On
        # 由于答案只能来源于非空的一侧，所以逻辑比取最大复杂一些
        if not root:
            return 0
        if not root.left and not root.right:
            return 1 # 必须得是叶子节点才能算好的
        if not root.left:
            return self.minDepth(root.right)+1
        elif not root.right:
            return self.minDepth(root.left)+1
        else:
            return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

404. 左叶子之和

https://leetcode.cn/problems/sum-of-left-leaves/description/

# 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 sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        # 时间：遍历所有节点 On
        # 空间：最坏情况下，节点都在单边，On
        # 左叶子，必须是叶子节点的同时也是左节点才行
        if not root:
            return 0
        if root.left and not root.left.left and not root.left.right:
            return root.left.val + self.sumOfLeftLeaves(root.right)
        return self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)

112. 路径总和

https://leetcode.cn/problems/path-sum/description/

# 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:
        # 时间：遍历所有节点 On
        # 空间：最坏情况下，节点都在单边，On
        if not root:
            return False
        targetSum -= root.val 
        if targetSum == 0 and not root.left and not root.right: # 到叶子节点刚好为0才对
            return True 
        return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)

129. 求根节点到叶节点数字之和

https://leetcode.cn/problems/sum-root-to-leaf-numbers/description/

# 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 sumNumbers(self, root: Optional[TreeNode]) -> int:
        # 时间：遍历所有节点 On
        # 空间：最坏情况下，节点都在单边，On
        def dfs(root: Optional[TreeNode], carry:int):
            carry *= 10
            carry += root.val
            # print(carry)
            if not root.left and not root.right:
                return carry
            elif not root.left:
                return dfs(root.right, carry)
            elif not root.right:
                return dfs(root.left, carry)
            else:
                return dfs(root.left, carry) + dfs(root.right, carry)
        
        return dfs(root, 0)

1448. 统计二叉树中好节点的数目

https://leetcode.cn/problems/count-good-nodes-in-binary-tree/description/

# 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 goodNodes(self, root: Optional[TreeNode]) -> int:
        # 时间：遍历所有节点 On
        # 空间：最坏情况下，节点都在单边，On
        ans = 0
        def dfs(root: Optional[TreeNode], rec_max:int): # 开始至少一个点
            if not root:
                return

            if rec_max <= root.val:
                nonlocal ans 
                ans += 1
                rec_max = root.val 
            dfs(root.left, rec_max)
            dfs(root.right, rec_max)
        

        dfs(root, -1e5)
        return ans

987. 二叉树的垂序遍历

https://leetcode.cn/problems/vertical-order-traversal-of-a-binary-tree/description/

# 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 verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        # 时间：遍历一遍树，再对每个列做了排序，算Onlogn
        # 空间：最坏情况下，节点都在单边，On
        group = defaultdict(list)
        min_col = 0 # 用于确认最小列的值，加上group的长度就知道有多少列，中间不会空

        def dfs(root, row, col):
            if not root:
                return 
            nonlocal min_col
            if min_col > col:
                min_col = col 
            group[col].append((row, root.val))
            dfs(root.left, row+1, col-1)
            dfs(root.right, row+1, col+1)
            
        dfs(root, 0, 0)
        ans = []
        for i in range(min_col, min_col+len(group)):
            g = group[i]
            g.sort() # 会默认先按row排序，相同时按照值排序
            ans.append([v for _, v in group[i]])
        return ans