Binary Tree Problem-Solving Approaches

When solving binary tree problems, two primary thinking patterns are commonly used:

1. Traversal-Based Approach: This approach focuses on whether the solution can be obtained by traversing the binary tree once. Typically, a traversal function (such as pre-order, in-order, or post-order) is combined with external variables. This method is suitable for cases where the same operasion needs to be performed on each node.

2. Problem Decomposition Approach: This approach emphasizes whether the solution can be derived by defining a recursive functon that computes answers from subproblems (subtrees). In this mode, you need to consider how to define the recursive function and how to utilize its return values. By continuously decomposing subproblems, the entire problem is eventually solved.

Regardless of the approach, it's essential to consider what each individual binary tree node needs to do and when to do it (pre-order, in-order, or post-order position). In recursive functions, you only need to focus on the current node, as recursion will perform the same operation on all nodes.

Binary tree algorithms are fundamental. For example, classic sorting algorithms like quicksort and mergesort can be viewed as pre-order and post-order traversals of a binary tree. Understanding these algorithms as special treatments of binary tree nodes—where pre-order operations are performed up on entering a node, post-order upon leaving, and in-order between left and right subtree traversals—can deepen your comprehension of advanced algorithms and extend binary tree thinking to other domains like dynamic programming, backtracking, divide-and-conquer, and graph algorithms.

1. Maximum Depth of a Binary Tree

Problem Description

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

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

Input: root = [1,null,2]
Output: 2

Constraints:

• The number of nodes is in the range [0, 10^4].
• -100 <= Node.val <= 100

Solution and Code

The maximum depth of a binary tree can be derived from the maximum depth of its subtrees, which aligns with the problem decomposition approach.

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

Result

2. Binary Tree Preorder Traversal

Problem Description

Given the root of a binary tree, return the preorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3]
Output: [1,2,3]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [1,2]

Example 5:

Input: root = [1,null,2]
Output: [1,2]

Constraints:

• The number of nodes is in the range [0, 100].
• -100 <= Node.val <= 100

Solution and Code

Preorder traversal follows the root-left-right sequence, which can be implemented recursively.

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        if (root == null) return result;
        result.add(root.val);
        result.addAll(preorderTraversal(root.left));
        result.addAll(preorderTraversal(root.right));
        return result;
    }
}

Result