We’ve explained the core idea of DFS, and that’s it, and we’ve again promoted the idea of a step-by-step approach, of going from the basic solution to breaking it down.

Recently, WHEN I was brushing Leetcode, I also brushed a lot of problems related to binary trees. Most of them had similar routines, from root node to leaf node from top to bottom, and I also encountered some new ones. So our main purpose today is to take a look at some of the more difficult problems in DFS, to see how some of the more novel problems examine the understanding of DFS, to see how they diverged from our original problem template to the current problem, to see if that’s the case.

Let’s start with a modest warm-up: given a binary tree, you need to calculate its diameter. The diameter length of a binary tree is the maximum of the path length of any two nodes. This path may or may not go through the root.

At first glance, my intuition tells me that if you want to find a path in a binary tree, and you want to maximize the diameter, that path must be a big circle between two leaves. Then we’ll probably have to do a depth-first search.

So the ground rules are set, and all that remains is to think differently. This is probably the longest path that doesn’t go through the root node, which is going to be a hassle, and we’re going to have to figure out how to deal with it. Also calculate the length of each path and record a maximum value. About these two points, we will further subdivide the specific steps on this basis:

1. At each step, we need to get the depth of the left and right children of the current node, just by doing two recursions.
2. The depth of the current node is the maximum depth of the left and right nodes +1.
3. The current node diameter is the left node depth + right node depth +1. So we’re going to calculate at each node what the longest diameter is going through that node. We can use a global variable to save the longest diameter so that at the end we can get the final longest diameter.

Everything is ready! Let’s try to write it out:

``````public static int findDiameter(TreeNode root) {
calculateHight(root);
return treeDiameter;
}

private static int calculateHight(TreeNode currentNode) {
if (currentNode == null)
return 0;

int leftTreeHeight = calculateHight(currentNode.left);
int rightTreeHeight = calculateHight(currentNode.right);

// The diameter of the current node is equal to the left child depth + the right child depth +1
int diameter = leftTreeHeight + rightTreeHeight + 1;

// Update the global maximum diameter
treeDiameter = Math.max(treeDiameter, diameter);

// Returns the maximum depth of the current node used to calculate the diameter of the parent node
return Math.max(leftTreeHeight, rightTreeHeight) + 1;
}
Copy the code``````

It’s a familiar recipe! Each time we return the maximum depth of the current node for the parent node to calculate the depth and maximum diameter, step by step, finally can calculate the maximum diameter. It’s nice to add constraint handling to basic DFS recursion.

I was happy when I solved it. (After all, it proves that the bull I blew was right, haha) So we’ll feel a lot better when we get to the next one. Given a nonempty binary tree, return the sum of its maximum paths.

Now that we’ve got the hang of it, we can do the same thing we did in DFS, just replace the depth code with the sum code, and ignore the negative sum paths for maximum value.

So we can change the logic directly:

``````public static int findMaximumPathSum(TreeNode root) {
globalMaximumSum = Integer.MIN_VALUE;
findMaximumPathSumRecursive(root);
return globalMaximumSum;
}

private static int findMaximumPathSumRecursive(TreeNode currentNode) {
if (currentNode == null)
return 0;

int maxPathSumFromLeft = findMaximumPathSumRecursive(currentNode.left);
int maxPathSumFromRight = findMaximumPathSumRecursive(currentNode.right);

// Ignore paths with negative sums
maxPathSumFromLeft = Math.max(maxPathSumFromLeft, 0);
maxPathSumFromRight = Math.max(maxPathSumFromRight, 0);

// The sum of the current nodes is the sum of the left children plus the right children plus the value of the current node
int localMaximumSum = maxPathSumFromLeft + maxPathSumFromRight + currentNode.val;

// Update global variables
globalMaximumSum = Math.max(globalMaximumSum, localMaximumSum);

// The maximum sum of the current node is equal to the maximum value of the left and right children plus the value of the current node
return Math.max(maxPathSumFromLeft, maxPathSumFromRight) + currentNode.val;
}
Copy the code``````

Both of these problems are O(N) in time and space. Are you happy? Even though Leetcode changed us, we firmly grasped the core and did not let go. No matter how complicated the problem condition was, we could deduce it step by step.

Hope to let you gain, Happy coding~