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

视频学习记录

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

• 承接上篇 【基础算法精讲-学习记录】二叉树1，本期是对于二叉树中递归的灵活运用，只要简单调整，之前的 dfs 遍历也能用于判断两个二叉树是否相同，或者一个二叉树是否对称这种。

• 总之就是别被全局的复杂吓住，梳理好单个节点上下关系就能写出递归。

例题和课后作业代码记录

100. 相同的树

https://leetcode.cn/problems/same-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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # 时间：遍历整个树On
        # 空间：最坏情况下n次嵌套，On
        if p is None or q is None:
            return p is q # 只有两边都为空才能True，否则False
        return p.val==q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

101. 对称二叉树

https://leetcode.cn/problems/symmetric-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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        # 时间：遍历整个树On
        # 空间：最坏情况下n次嵌套，On
        def dfs_symmetric(p, q):
            if p is None or q is None:
                return p is q # 只有两边都为空才能True，否则False
            return p.val==q.val and dfs_symmetric(p.left, q.right) and dfs_symmetric(p.right, q.left)
        return dfs_symmetric(root.left, root.right)

110. 平衡二叉树

https://leetcode.cn/problems/balanced-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 isBalanced(self, root: Optional[TreeNode]) -> bool:
        # 时间：遍历整个树On
        # 空间：最坏情况下n次嵌套，On
        def getDepth(root): # 求节点高度，如果不平衡传-1（高度都是正数）
            if not root:
                return 1 
            left = getDepth(root.left)
            right = getDepth(root.right)
            if left == -1 or right == -1:
                return -1 

            if abs(left-right) > 1:
                return -1

            return max(left, right)+1
        
        return getDepth(root)!=-1

199. 二叉树的右视图

https://leetcode.cn/problems/binary-tree-right-side-view/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 rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        # 时间：遍历整个树On
        # 空间：最坏情况下n次嵌套，On
        ans = []
        def dfs(root: Optional[TreeNode], carry:int):
            if not root:
                return 
            nonlocal ans 
            if carry >= len(ans):
                ans.append(root.val)
            carry += 1
            dfs(root.right, carry)
            dfs(root.left, carry)
        dfs(root, 0)
        return ans

965. 单值二叉树

https://leetcode.cn/problems/univalued-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 isUnivalTree(self, root: Optional[TreeNode]) -> bool:
        # 时间：遍历整个树On
        # 空间：最坏情况下n次嵌套，On
        def dfs(root, val):
            if not root:
                return True
            if root.val != val:
                return False
            return dfs(root.left, val) and dfs(root.right, val)

        return dfs(root, root.val)

951. 翻转等价二叉树

https://leetcode.cn/problems/flip-equivalent-binary-trees/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 flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        # 时间：遍历整个树On
        # 空间：最坏情况下n次嵌套，On
        if not root1 or not root2:
            return root1 is root2
        
        return root1.val == root2.val and (
            (
                self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)) or 
                (self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))
            )

226. 翻转二叉树

https://leetcode.cn/problems/invert-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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # 时间：遍历整个树On
        # 空间：最坏情况下n次嵌套，On
        if not root:
            return None 
        self.invertTree(root.left)
        self.invertTree(root.right)
        root.left, root.right = root.right, root.left 
        
        return root

617. 合并二叉树

https://leetcode.cn/problems/merge-two-binary-trees/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 mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        # 时间：遍历整个树On
        # 空间：最坏情况下n次嵌套，还建了整个树，On
        if root1 is None or root2 is None:
            if root1 is None:
                return root2 
            else:
                return root1 
        left = self.mergeTrees(root1.left, root2.left)
        right = self.mergeTrees(root1.right, root2.right)
        
        cur = TreeNode(root1.val+root2.val, left, right) 

        return cur

2331. 计算布尔二叉树的值

https://leetcode.cn/problems/evaluate-boolean-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 evaluateTree(self, root: Optional[TreeNode]) -> bool:
        # 时间：遍历整个树On
        # 空间：最坏情况下n次嵌套，On
        if root.val < 2: # 开始至少一个点，只要叶子停了就不用判断空
            return True if root.val == 1 else False 
        
        return self.evaluateTree(root.left) or self.evaluateTree(root.right) if root.val == 2 else self.evaluateTree(root.left) and self.evaluateTree(root.right) 

508. 出现次数最多的子树元素和

https://leetcode.cn/problems/most-frequent-subtree-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 findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:
        # 需要先得到所有的子树元素和，维护哈希表，最后再取哈希表值按出现次数排序降序
        # 时间：遍历整个树，有对每个子树元素和以及对应频率排序，最坏情况下Onlogn，最好On
        # 空间：存储整个树的子树元素和以及对应频次，加上衍生存储，On
        rec = defaultdict(int)
        def dfs(root):
            if not root:
                return 0 
            l = dfs(root.left)
            r = dfs(root.right)
            cur = l+r+root.val
            
            rec[cur] += 1
            return cur 

        dfs(root)
        
        cnt = []
        for s, c in rec.items():
            cnt.append((c, s))
        cnt.sort(reverse=True) # 非升序，按频次
        # print(rec, cnt)
        ans = [cnt[0][1]]
        for pair in cnt[1:]:
            if pair[0] == cnt[0][0]: # 频次相同的也加上
                ans.append(pair[1])
            else:
                break
        
        return ans

1026. 节点与其祖先之间的最大差值

https://leetcode.cn/problems/maximum-difference-between-node-and-ancestor/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 maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        # 时间：遍历整个树On
        # 空间：最坏情况下n次嵌套，On
        v = 0 
        def dfs(root, min_val, max_val):
            if not root:
                return 

            nonlocal v 
            if abs(max_val - root.val) > v or abs(root.val - min_val) > v:
                v = max(abs(max_val - root.val), abs(root.val - min_val))

            max_val = max(max_val, root.val)
            min_val = min(min_val, root.val)

            dfs(root.left, min_val, max_val)
            dfs(root.right, min_val, max_val)

        dfs(root, root.val, root.val)
        return v

1372. 二叉树中的最长交错路径

https://leetcode.cn/problems/longest-zigzag-path-in-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 longestZigZag(self, root: Optional[TreeNode]) -> int:
        # 时间：遍历整个树On
        # 空间：最坏情况下n次嵌套，On，普通是Oh，h是树的高度
        ans = 0
        def dfs(root):
            if not root:
                return 0, 0
            _, left_r = dfs(root.left) 
            right_l, _ = dfs(root.right)

            nonlocal ans
            ans = max(max(left_r, right_l), ans)

            return left_r + 1, right_l + 1 # 返回值是左节点和右节点能走的最长值
        dfs(root)
            
        return ans

1080. 根到叶路径上的不足节点

https://leetcode.cn/problems/insufficient-nodes-in-root-to-leaf-paths/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 sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:
        # 时间：遍历整个树On
        # 空间：最坏情况下n次嵌套，On，普通是Oh，h是树的高度
        def dfs(root, carry):
            carry += root.val # 保证 root 非空
            if not root.left and not root.right:
                if carry >= limit:
                    return True, root 
                else:
                    return False, None
            
            valid = False
            if root.left:
                l_valid, root.left = dfs(root.left, carry) 
                valid = l_valid or valid 
            
            if root.right:
                r_valid, root.right = dfs(root.right, carry)
                valid = r_valid or valid 
            
            return valid, root if valid else None
        
        _, root = dfs(root, 0)
        return root