【 Algorithm 题】 recursive binary tree depth

Binary tree depth algorithm, is a binary tree in the comparison of the basic algorithm. That’s Problem 104 in LeetCode.

And then you’ll see that some of the algorithms in LeetCode later on require variations of this algorithm, like problem 110 and 543. These two problems, if you know the recursive procedure of the binary tree depth algorithm, are easy to do.

About the binary tree related knowledge, you can see my article: Data Structure 】 tree simple analysis summary (attached js implementation)

Topic describes

Given a binary tree, find its maximum depth.

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

Note: A leaf node is a node with no child nodes.

Example: given a binary tree [3,9,20,null,null,15,7],

3 / \ 9 20 / \ 15 7 Returns its maximum depth of 3.Copy the code

Note that the binary tree is stored in chains, not arrays.

1. What is recursion

Before we solve this problem, let’s first understand what recursion is (if you already know, please skip this section).

Then let’s start Wang reciting the BA text (Jing).

Recursion is divided into “recursion” and “return”. “Recursion” means pass in, “return” means a function completes and solves a subproblem. Recursion is implemented by constantly dividing the problem into subproblems, and by solving the subproblems, the original problem is finally solved.

The core of recursion is the recursion formula, and when we analyze the recursion formula, the recursion problem is solved. Recursion is a widely used programming technique that can be used in many ways, such as depth-first traversal (this is the case in this case) and fore-and-middle traversal of binary trees.

Recursion requires three conditions:

1. Can be decomposed into multiple subproblems;
2. In addition to the different data scale, the solution method of subproblems is unchanged;
3. Recursive termination conditions exist.

The thing about recursion is that the code is A little bit cleaner, and most of the time it’s hard for you to understand what’s going on in A recursion, because it doesn’t fit the human mind, but you don’t really have to, you just have to know that B and C have been solved, and you can derive A, Don’t worry about how B and C are solved by the subproblem (because it’s the same!). .

Second, if you recurse too deeply, you may run out of memory. Because there are many call records to keep when recursing, a call stack is maintained, and when the stack is too large for the available memory space, a memory overflow occurs, called a stack overflow. There are four solutions:

1. When the recursive call exceeds a certain depth, the error is reported directly, and the recursion is no longer continued. The exact depth of the overflow cannot be calculated, and the error will cause the program to stop running, so while this scheme does prevent overflow, it does not seem to be useful.
2. Cache repeats. Recursion may repeatedly call the result of an already solved f(k), in which case the f(k) should be cached, usually in a hash table (which can be achieved in JS via an object). When we execute f(k) the second time, we just get it directly from the cache.
3. Change to non-recursive code. It’s essentially a loop. The modified loop is essentially recursion, except that we manually implement the recursion stack. A looping code implementation is more complex than recursion and less elegant.
4. Tail recursion. A technique of tail-call optimization is used, depending on whether the runtime environment provides this optimization. In the case of tail-call optimization, if the last step of function A calls another function B, no record of A’s call (such as some of A’s internal variables) is retained when entering B, so that the stack is not so long that the stack overflows.

Speaking of recursion, we have to mention a classic problem of recursion, which is the “stair climbing problem”, corresponding to Problem 70 of LeetCode.

The problem description for climbing stairs is: Suppose you are climbing stairs. It takes n orders to get to the top. You can climb one or two steps at a time. How many different ways can you climb to the top of the building?

First you could list n = 1, n = 2… And try to find a pattern.

This is where we start to see some patterns. So the way to go to order 3 is the sum of order 2 and order 1. Why is that? We have to find the essence through the phenomenon, and the essence is, to get to the NTH order, you have to first go to the N-1 and then climb one step, or you have to go to the N-2 and then climb two steps.

So we have this recursive formula: f(n) = f(n-1) + f(n-2).

Recursive writing:

var climbStairs = function(n) {
    let map = {};
    function f(n) {
        if (n < 3)  return n;
        if (map[n]) return map[n];
        
        let r =  f(n- 1) + f(n - 2);
        map[n] = r;
        return r;
    }
    return f(n)
Copy the code

Because f of n is equal to f of n minus 1 plus f of n minus 2. This is f of n minus 1, which is f of n minus 2 plus f of n minus 3. Here, f(n-2) is executed twice, so you need to cache the result of f(n-2) into the map object to reduce the computation time.

Writing in cycles:

var climbStairs = function(n) {
    if (n < 3) return n;

    let step1 = 1.// The previous step
        step2 = 2;  / / step

    let tmp;
    for (let i = 3; i <= n; i++) {
        tmp = step2;
        step2 = step1 + step2;
        step1 = tmp;
    }
    return step2;

};
Copy the code

2. Problem analysis

So with that recursion out of the way, let’s analyze the problem.

First, let’s try to figure out the recursion. First of all, we know that every node in a binary tree, except the leaf node, has a left and right subtree. So if we know the depth of the left and right subtrees, find the maximum between them, and then add one, isn’t that the depth of the binary tree? Secondly, the height of the binary tree with the root node of the leaf node is 1, and we can use this as the end condition of the recursion.

3. Code implementation

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/** * @param {TreeNode} root * @return {number} */
var maxDepth = function(root) {
    function f(node) {
        if(! node)return 0;
        return Math.max(f(node.left), f(node.right)) + 1;
    }
    return f(root);
};
Copy the code

We’re using depth-first traversal, which is going from the root to the leaf along the binary tree. Also, because there is no double counting, there is no need to cache the results. Also, since there are no extra variables to save, we can write the maxDepth function as a recursive function directly.

4. Extension: How to find the depth of the binary tree of array storage?

For more information on how to store binary trees in arrays (sequential storage method), see the article I mentioned earlier.

Finding the depth of a binary tree represented by an array can be thought of as finding the depth of the corresponding complete binary tree.

Before we do that, let’s see how to find the depth k of a full binary tree with n nodes.

The rule is obvious. By using the geometric sequence summation formula, we get k = Math.log2(n+1), where k is the depth and n is the number of nodes in the full binary tree. Then, for a complete binary tree, round k up: k = math.ceil (math.log2 (n+1)).

So for a binary tree of length n stored by the sequential storage method, its height K is:

k = Math.ceil( Math.log2(n+1) )
Copy the code

(Note that the array stores nodes from 0.)

reference

1. Ruan Yifeng’s web log — Tail call optimization
2. The beauty of the data structure and algorithm: 10 | recursive: how to find out “at the end of the referee,” with three lines of code?