Recursion

Binary Tree

104. Maximum Depth of Binary Tree: leetcode.cn/problems/maximum-depth-of-binary-tree/

Given the root of a binary tree, return its maximum depth. A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Approach & Solution: Use recursion to traverse the left and right subtrees and calculate the maximum depth. For each node, compare the depths of the left and right subtrees and return the larger one plus 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

Complexity Analysis:

• Time Complexity: O(n), where n is the number of nodes in the tree, traversing each node once.
• Space Complexity: O(h), where h is the height of the tree, as the maximum depth of the recursion stack is h.

100. Same Tree: leetcode.cn/problems/same-tree/

Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Approach & Solution: Recursively traverse every node of both trees to check if the node values and the left/right subtrees are identical.

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)

Complexity Analysis:

• Time Complexity: O(n), where n is the number of nodes in the tree, traversing each node once.
• Space Complexity: O(h), the maximum depth of the recursion stack is h, where h is the height of the tree.

101. Symmetric Tree: leetcode.cn/problems/symmetric-tree/

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Approach & Solution: Recursively check if the left and right subtrees are symmetric. The conditions for recursion are:

• The value of the root of the left subtree equals the value of the root of the right subtree.
• The left child of the left subtree is symmetric to the right child of the right subtree, and the right child of the left subtree is symmetric to the left child of the right subtree.

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. Balanced Binary Tree: leetcode.cn/problems/balanced-binary-tree/

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is defined as a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Approach & Solution: Recursively calculate the height of the left and right subtrees for each node and check if the difference in height exceeds 1. If it exceeds 1, return -1 to indicate it is not balanced; otherwise, return the depth of the current node.

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. Binary Tree Right Side View: leetcode.cn/problems/binary-tree-right-side-view/

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Approach & Solution: Use Depth First Search (DFS), traversing nodes level by level. The first node encountered at each depth (when traversing right-to-left) or simply prioritizing the right child first ensures the right view nodes are captured. Author’s note: The code below actually uses a specific DFS traversal order (Right -> Left) and captures the first node encountered at a new depth.

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

Optimization Summary:

• Adopt recursive traversal methods to solve problems like binary tree depth and symmetry through recursion.
• Time complexity is mostly O(n), where n is the number of nodes. Space complexity is O(h), where h is the height of the tree, representing the recursion stack depth.