递归

二叉树

104. 二叉树的最大深度：leetcode.cn/problems/maximum-depth-of-binary-tree/

给定一个二叉树 root，返回其最大深度。 二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

思路与解答： 利用递归遍历左右子树，计算出最大深度。对于每个节点，左子树和右子树的深度进行比较，返回其中较大的一个加1。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def maxDepth(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        if root is None:
            return 0
        left_height = self.maxDepth(root.left)
        right_height = self.maxDepth(root.right)
        return max(left_height, right_height) + 1

复杂度分析：

• 时间复杂度：O(n)，其中 n 为树中节点的数量，遍历每个节点一次。
• 空间复杂度：O(h)，其中 h 是树的高度，递归栈的最大深度为 h。

100. 相同的树：leetcode.cn/problems/same-tree/

给定两棵二叉树的根节点 p 和 q，判断它们是否相同。 如果两棵树的结构和节点值都相同，则认为它们是相同的。

思路与解答： 通过递归遍历两棵树的每个节点，判断节点值和左右子树是否相同。

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: Optional[TreeNode]
        :type q: Optional[TreeNode]
        :rtype: bool
        """
        if p is None or q is None:
            return p is q
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

复杂度分析：

• 时间复杂度：O(n)，其中 n 是树中节点的数量，遍历每个节点一次。
• 空间复杂度：O(h)，递归栈的最大深度为 h，其中 h 是树的高度。

101. 对称二叉树：leetcode.cn/problems/symmetric-tree/

给定一个二叉树的根节点 root，检查它是否是对称的（即左右子树是否镜像对称）。

思路与解答： 通过递归的方式检查左右子树是否对称，递归的条件是：

• 左子树的根节点值与右子树的根节点值相等。
• 左子树的左子树与右子树的右子树相对称，左子树的右子树与右子树的左子树相对称。

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def recur(p, q):
            if p is None or q is None:
                return p is q
            return p.val == q.val and recur(p.left, q.right) and recur(p.right, q.left)
        return recur(root.left, root.right)

110. 平衡二叉树：leetcode.cn/problems/balanced-binary-tree/

给定一个二叉树，判断它是否是平衡二叉树。 平衡二叉树指的是每个节点的左右子树高度差的绝对值不超过 1。

思路与解答： 通过递归计算每个节点的左右子树高度，并判断左右子树高度差是否超过 1。如果超过 1，返回 -1，表示不是平衡二叉树；否则返回该节点的深度。

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def maxDepth(root):
            if root is None:
                return 0
            left_depth = maxDepth(root.left)
            if left_depth == -1:
                return -1
            right_depth = maxDepth(root.right)
            if right_depth == -1 or abs(left_depth - right_depth) > 1:
                return -1
            return max(left_depth, right_depth) + 1
        return maxDepth(root) != -1

199. 二叉树的右视图：leetcode.cn/problems/binary-tree-right-side-view/

给定一个二叉树的根节点 root，从右侧视角看，返回能够看到的节点值。 从上到下，按照从左到右的顺序返回。

思路与解答： 使用深度优先遍历，逐层遍历节点，每一层的第一个节点就是从右侧看到的节点。

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        def f(root, depth):
            if root is None:
                return None
            if len(ans) == depth:
                ans.append(root.val)
            f(root.right, depth + 1)
            f(root.left, depth + 1)
        f(root, 0)
        return ans

优化思路总结：

• 采用递归遍历方法，通过递归求解二叉树的深度、对称性等问题。
• 时间复杂度大多为 O(n)，其中 n 为节点数。空间复杂度为 O(h)，h 为树的高度，递归调用的深度。