Algorithm interview Replay: Binary Tree maximum Depth and DFS (bytes)

In computer science, a binary tree is a tree structure with at most two subtrees per node. Subtrees are usually called “left subtrees” and “right subtrees”. Binary trees are often used to implement binary search trees and binary heaps. Trees are slightly more complex than linked lists because linked lists are linear data structures, whereas trees are not. Many of the tree problems can be solved by breadth-first or depth-first searches.

In this series, we will use some examples to learn the classic operation of binary trees!

01. Topic analysis

Note: Leaf nodes are nodes that have no child nodes.

Example:

Given a binary tree [3,9,20, NULL, NULL,15,7], 3 / \ 9 20 / \ 15 7Copy the code

This series is a must!

02, Recursive solution

We know that ** the depth of each node is related to the depth of its left and right subtrees, and is equal to the maximum depth of its left and right subtrees plus 1 **. That is:

maxDepth(root) = max(maxDepth(root.left),
maxDepth(root.right)) + 1

For example, [3,4,20,null,null,15,7] :

<1> To solve the maximum depth of the root node, we need to solve the depth of its left and right subtrees

<2> We see that. A subtree with root 4 has no left and right nodes and a depth of 1. The depth of a subtree with root 20 also depends on the depth of its left and right subtrees.

Therefore, we can get that the maximum depth of the root node is:

maxDepth(root-3) =max(**maxDepth**(sub-4),**maxDepth**(sub-20))+1 MaxDepth = Max (1, Max (* * * * (sub - 15), maxDepth * * * * (sub - 7)) + 1) + 1 = Max (1, Max (1, 1) + 1) + 1 = Max (1, 2) + 1 = 3Copy the code

According to the analysis, we solved the code recursively as follows:

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

func max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}
Copy the code

03, DFS

In fact, the recursion we used above is essentially using the idea of DFS. DFS: Depth First Search. For binary trees, it traverses the nodes of the tree as deep as possible, searching branches of the tree until all nodes reachable from the source node have been found.

As shown in the above binary tree, its access order is:

A-B-D-E-C-F-G

A-B-D-E-C-F-G

Now, let’s think about the question, right? Although we completed the problem in a recursive way according to the idea of DFS. But the disadvantages of this approach are obvious. Because in recursion, if the hierarchy is too deep, we are likely to hold too many temporary variables, resulting in stack overflow. This is why we generally don’t use recursion in background code. If you don’t understand, let’s elaborate below:

In fact, the parameters of a function call are passed through the stack space, occupying the thread’s stack resources during the call. And recursive call, only go to the end of the last point after function can in turn out, and did not reach the final point before the end of the occupancy of stack space has not been released, if the number of recursive calls too much, can lead to exceed the maximum thread take up the stack of resources, leading to stack overflow, causing the abnormal exit of the program.

So, we come up with the following topic: how to convert recursive code into non-recursive form. Keep in mind here that 99% of recursion to non-recursion can be done on a stack.

The code for non-recursive DFS is as follows:

private List<TreeNode> traversal(TreeNode root) {     List<TreeNode> res = new ArrayList<>(); 
    Stack<TreeNode> stack = new Stack<>(); 
    stack.add(root); 
    while(! stack.empty()) { TreeNode node = stack.peek(); res.add(node); stack.pop();if(node.right ! =null) {
           stack.push(node.right);
           }
        if(node.left ! =null) { stack.push(node.left); }}return res;
}
Copy the code

The only thing that needs to be emphasized in the above code is, why do I need to press the data right and then left? This is because we need to push the data we accessed first onto the stack (think about the stack).

If you don’t understand the code, look at the following image:

1: First push A onto the stack

2: A pops the stack and pushes C and B onto the stack (pay attention to the order)

3: B pops the stack and pushes E and D onto the stack

4: D, E, C, g, F into the stack

5: F, G bomb stack

So that’s the end of non-recursive DFS. So how do we solve this problem in a non-recursive DFS way? Believe already very simple, leave homework, please practice by yourself!

I’ve compiled all the problems I’ve written into an e-book, complete with illustrations for each problem. Click to download