The Way to Start LeetCode

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);
  }

preorder


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

inoder


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

postorder

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.


    private int maxIndex(int[] nums, int left, int right) {
        int max = left;
        for (int i = left; i <= right; i++) {
            if (nums[i] > nums[max]) {
                max = i;
            }
        }
        return max;
    }

We then apply this method within the preorder traversal structure, making sure to handle the base or exit cases appropriately.


    private TreeNode constructMaximumBinaryTree(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        if (left == right) {
            return new TreeNode(nums[left]);
        }
        int middle = maxIndex(nums, left, right);
        TreeNode node = new TreeNode(nums[middle]);
        node.left = constructMaximumBinaryTree(nums, left, middle - 1);
        node.right = constructMaximumBinaryTree(nums, middle + 1, right);
        return node;
    }

Let’s try a postorder traversal problem: 114. Flatten Binary Tree to Linked List. The hint in this problem states that the 'linked list' should follow the same order as a preorder traversal of the binary tree so that we can naturally know to use postorder traversal. The key steps are to cut the left node and connect it to the right of the root. This bottom-up approach, where we handle the nodes from leaves back to the root, aligns with the logic of postorder traversal.

Before writing the code, let's ask ourselves again: what's the difference between the code for preorder traversal and postorder traversal? It's the position of res.add(root.val). The position of this line determines the order of traversal, and it’s where we should place our core logic. Here's the code:


    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        flatten(root.left);
        flatten(root.right);
        TreeNode right = root.right;
        root.right = root.left;
        root.left = null;
        while (root.right != null) {
            root = root.right;
        }
        root.right = right;
    }

Lastly, we have inorder traversal, which is particularly useful for binary search trees (BSTs). Let’s look at the 538. Convert BST to Greater Tree. In this problem, we add the value of each right node to its root, meaning we need to visit the right nodes before the left ones. This approach is a reverse version of inorder traversal.


    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        convertBST(root.right);
        sum += root.val;
        root.val = sum;
        convertBST(root.left);
        return root;
    }

One traversal method I haven't mentioned is BFS (breadth-first search). In tree problems, we use BFS primarily to traverse nodes level by level. A good example is 102. Binary Tree Level Order Traversal:


    public List<List<Integer>> levelOrder(TreeNode root) {
        Deque<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new LinkedList<>();
            int count = queue.size();
            for (int i = 0; i < count; i++) {
                TreeNode node = queue.pop();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            res.add(level);
        }
        return res;
    }

We use a queue to solve these types of problems. We simply visit one level at a time, implement our core logic, and then move on to the next level.

To sum up, when encountering a new type of LeetCode problem, it's essential to establish a structured approach for effective problem-solving and to know when to apply each method. For tree problems, preorder traversal is useful for top-down traversal, while postorder traversal serves the opposite purpose. Inorder traversal is specifically beneficial for binary search trees, and BFS is ideal for level-by-level traversal. And remember, consistent practice is key! Now, try these two questions to test your understanding of tree problems:

105. Construct Binary Tree from Preorder and Inorder Traversal

103. Binary Tree Zigzag Level Order Traversal