【2025-03-02】基础算法：二叉树 相同 对称 平衡 右视图

# 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:
        # 问题可以分解成：1，判断根节点是否相同；2，再对左右子树进行比较
        # 结束条件：当节点为空（这个时候也需要比较）
        if p is None or q is None:
            return p is q # p is None and q is None 的简写
        return q.val == p.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

# 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:
        # 把树分成两棵树，即判断：
        # 1, 根节点是否相同 2, 左边左子树是否等于右边右子树 3, 左边右子树是否等于右边左子树
        # 结束：节点为空

        def isSym(left, right):
            if left is None or right is None:
                return left is right
            return left.val == right.val and isSym(left.left, right.right) and isSym(left.right, right.left)
        
        return isSym(root.left, root.right)

# 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:
        # 判断是否为平衡树需要利用左右子树的高度差
        # 不断递归遍历子树，寻找到不是平衡树时，剪枝，将结果一直返回到最顶层
        # 否则，若不是非平衡就是平衡

        def get_height(root):
            # 后续遍历 + 将结果往上传
            # 添加剪枝操作，当发现非平衡返回 -1 然后往上传（因为深度>=0，所以用-1）
            if root is None: return 0
            l_height = get_height(root.left)
            if l_height == -1: return -1
            r_height = get_height(root.right)
            if r_height == -1: return -1
            return max(l_height, r_height) + 1 if abs(l_height - r_height) <= 1 else -1

        return get_height(root) != -1

# 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]:
        # 从上到下，先找右子树，再找左子树
        # 如果深度是首次遇到，就添加
        ans = []
        def dfs(node, depth):
        	# 利用depth记录深度
            if node is None:
                return
            if depth == len(ans):
                ans.append(node.val)
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)
        dfs(root, 0)
        return ans

# 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:
        val = root.val
        def dfs(node):
            if node is None: return True
            if node.val != val: return False
            return dfs(node.left) and dfs(node.right)
        return dfs(root)

# 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:
        # 有限次的左右交换，即：子树相同或者子树对称
        if root1 is None or root2 is None: return root1 is root2
        if root1.val != root2.val: return False
        return (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))

# 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]:
        # 对于根节点，交换左右儿子
        # 对于根节点的子树，也要交换左右儿子
        if root is None:
            return
        left = self.invertTree(root.left) # 翻转左子树
        right = self.invertTree(root.right)
        root.right = left # 将翻转好的 left 交换到右孩子的位置
        root.left = right
        return root  # root 已经是翻转好的

# 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]:
        # 将第二棵合并到第一棵上
        if root2 is None:
            return root1
        if root1 is None:
            return root2
            
        # 中间这一段可以合并写到 TreeNode 中，即：
        # return TreeNode(root1.val + root2.val,
        # self.mergeTrees(root1.left, root2.left),  
        # self.mergeTrees(root1.right, root2.right))
        
        root1.val = root1.val + root2.val
        L = self.mergeTrees(root1.left, root2.left)
        R = self.mergeTrees(root1.right, root2.right)
        root1.right = R
        root1.left = L
        return root1

# 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:
        if root.right is None and root.left is None:
            return True if root.val == 1 else False
        if root.val == 3:
            return self.evaluateTree(root.left) and self.evaluateTree(root.right)
        else:
            return self.evaluateTree(root.left) or self.evaluateTree(root.right)

# 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]:
        cnt = Counter()
        def dfs(node):
            nonlocal cnt
            # 求树元素和
            if node is None:
                return 0
            s = node.val + dfs(node.left) + dfs(node.right)
            cnt[s] += 1
            return s
        dfs(root)
        m =  max(cnt.values())
        return [key for key, value in cnt.items() if value == m]

# 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:
        ans = 0
        def dfs(node, mi, mx):
            nonlocal ans
            if node is None: return 
            mx = max(node.val, mx)
            mi = min(node.val, mi)
            ans = max(ans, node.val - mi, mx - node.val) 
            dfs(node.left, mi, mx)
            dfs(node.right, mi, mx)
        dfs(root, root.val, root.val)
        return ans

# 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:
        # 对于每个节点有两种走法：
        # 1，继续走交错路径，2，重新开发新的路
        # 走交错路径时要遵守按不同的方向走，因此要记录上一次所走的方向
        ans = 0
        def dfs(node, is_right, length):
            # is_right 代表上一次走的右边
            nonlocal ans
            if node is None: return
            ans = max(ans, length)

            if is_right:
                dfs(node.left, False, length + 1) # 继续走
                dfs(node.right, True, 1) # 开发新路
            else:
                dfs(node.right, True, length + 1)
                dfs(node.left, False, 1)
        dfs(root, True, 0)
        return ans

# 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]:
        limit -= root.val
        if root.left is root.right:
            return None if limit > 0 else root
        if root.left:
            root.left = self.sufficientSubset(root.left, limit)
        if root.right:
            root.right = self.sufficientSubset(root.right, limit)
        return root if root.left or root.right else None # 判断节点是否要删除