I initially focused on solving various LeetCode problems for interviews, but I often find it challenging to confidently tackle every problem, even the popular ones. Instead of just practicing more problems, I’ve adopted a more effective strategy: approaching them by topic and summarizing the characteristics of each area.

A great starting point is tree problems. Trees are a unique type of directed graph where each node has at most two children, functioning similarly to an advanced linked list. By mastering how to solve tree problems, we can build a solid foundation for tackling challenges in other topics.

When facing a new problem type, the first step is to understand the underlying data structure or algorithm. Trees, as a specific type of data structure, often involve traversing their nodes. There are three types of traversal: preorder, inorder and postorder.

For the recursive implementation, the code of structure is straightforward; we simply need to adjust the position of res.add(root.val). Depending on when we add the root value—before the recursive calls for its children or after—we can achieve the desired traversal order.

  public void preorder(TreeNode root) {
      if (root == null) {
          return;
      }
      res.add(root.val);
      preorder(root.left);
      preorder(root.right);
  }

  public void inoder(TreeNode root) {
      if (root == null) {
          return;
      }
      inoder(root.left);
      res.add(root.val)
      inoder(root.right);
  }

  public void postorder(TreeNode root) {
      if (root == null) {
          return;
      }
      postorder(root.left);
      postorder(root.right);
      res.add(root.val);
  }

Traversal methods can also be implemented using a non-recursive approach with the help of a stack. For example, in preorder traversal, we continue moving to the left child until there are no more left nodes. At that point, the parent node is the last node we visited, and we proceed to explore its right child, if it exists, continuing the process until all nodes have been visited.

	public List<Integer> preorderTraversal(TreeNode root) {
		List<Integer> res = new LinkedList<>();
		Deque<TreeNode> stack = new LinkedList<>();
		
		while (root != null || !stack.isEmpty()) {
			while (root != null) {
				res.add(root.val);
				stack.push(root);
				root = root.left;
			}
			TreeNode cur = stack.pop();
			root = cur.right;
		}
		return res;
	}

Inorder traversal is similar to preorder traversal, with the main difference being the position of res.add(cur.val). In inorder traversal, we add the current node's value after visiting the left child but before moving to the right child.

	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> res = new LinkedList<>();
		Deque<TreeNode> stack = new LinkedList<>();
		
		while (root != null || !stack.isEmpty()) {
			while (root != null) {
				stack.push(root);
				root = root.left;
			}
			TreeNode cur = stack.pop();
			res.add(cur.val);
			root = cur.right;
		}
		return res;
	}

Postorder traversal can be seen as the reverse of preorder traversal. In preorder, we visit the nodes in the order of [middle, left, right], while in postorder, the order is [left, right, middle]. If we traverse the nodes in the preorder sequence [middle, right, left] and then reverse the result list, we obtain the postorder traversal.

  public List<Integer> postorderTraversal(TreeNode root) {
      LinkedList<Integer> res = new LinkedList<>();
      Deque<TreeNode> stack = new LinkedList<>();
      while (root != null || !stack.isEmpty()) {
          while (root != null) {
              stack.push(root);
              res.addFirst(root.val);
              root = root.right;
          }
          TreeNode cur = stack.pop();
          root = cur.left;
      }
      return res;
  }

There might be some confusion, but the next explanation will help clarify things. Let’s focus on the recursive versions. The different positions of res.add(root.val) correspond to different traversal orders. By simulating the traversal process, we can see that preorder traversal is top-down, postorder is bottom-up, and inorder traversal is particularly useful for binary search trees (BSTs). Understanding these distinctions can simplify our grasp of how each traversal method operates.

Ok, let’s get hands dirty.

654. Maximum Binary Tree. When constructing a tree, we build it from the root to the leaves, which is a top-down process. Therefore, preorder traversal is the appropriate choice for this problem. The root should be the maximum value, so we can write a method to find that maximum.