Being a rebellious programmer, I didn’t start with binary trees and then brush dynamic programming.

But first brush the foundation of dynamic programming, feel a little sorry for Labuladong’s algorithm cheat sheet authors.

primers

Since the brush problem, the first contact with trees from the Fibonacci series of problems began. It’s not the structure of the tree, it’s the thinking of the tree.

Recursive solution of Fibonacci sequence

f(n) = f(n-1) + f(n-2)

The complete graph is a tree, which can be optimized to reduce repetitive operations

You can even optimize to save only the first two states

When I saw this tree, I felt like I had suddenly discovered the secrets of the world. So I encountered a lot of problems to practice, such as N queen, sudoku, as if I felt that recursion, backtracking, iteration ah silly confused, as if as long as a routine, the code can be calm to run up.

Therefore, there has been no attention to the binomial tree related problems, these days to strengthen the binomial tree related body shape, slightly obtained, but there are also some entanglements, record here.

A vague uneasiness

The initial dilemma is, what is recursion? Why is it that there are many problems that I can do well with recursion, but once I don’t use recursion, I’m useless, as if I only know one stupid formula, and all problems can be solved so “superficially”.

This has troubled me for more than half a year, finally in today’s brush problem journey, has been solved. And that’s recursion the stack. In other words, the function itself is a very advanced stack. So advanced that you’re using it all the time without realizing that it’s essentially a stack.

Binary tree in order traversal leetCode 94

In order traversal recursion left root right root in the middle order traversal

Recursive solution left, root, right omitted

The iterative solution uses the while loop + stack

var inorderTraversal = function(root) {
    const res = [];
    const stack = [];
    while (stack.length || root) {
        while (root) {
            stk.push(root);
            root = root.left;
        }
        root = stk.pop();
        res.push(root.val);
        root = root.right;
    }
    return res;
};
Copy the code

All of today’s doubts begin with this iterative solution, where something is vaguely wrong, but you can’t tell. The problem is that the stack and our function calls seem to be different, and the difference, which I didn’t know at first, turns out to be that this is the better solution, which is a particular solution of the order traversal solution, rather than the traditional stack simulation of recursive calls to functions. What about a recursive call to a function simulated by a stack?

var inorderTraversal = function(root) { let stack = [] let result = [] stack.push(root) let tempNode,tempValue while(stack.length){ tempNode = stack.pop() if(tempNode===null){ if(stack.length){ result.push(stack.pop()) } continue }  stack.push(tempNode.right) stack.push(tempNode.val) stack.push(tempNode.left) } return result};Copy the code

The key break point here is that for the simulation of function scope, each set of push operations on the stack is simulating a recursive nesting of the function, and each set of push is another layer of nesting. Each set of POP operations simulates the actual execution of the function. For each set of POP operations, there is one more return and one less nested function. With that in mind, when you look at the iterative answer given by the problem, you don’t see it as something out of thin air, but more of an optimization. You won’t always be able to imagine the optimal solution, but the process of optimizing will take you closer and closer to the optimal solution.

Today’s harvest still has a lot of, but more is practice can make perfect, brush back already dizzy, feel a problem, do not know what method is better, stack can also do, recursion can also do, the queue can also do, thinking has gradually become stiff. Next time I get a chance, I’ll pay another visit to binary trees

Different binary search tree ⅱ leetcode 95

Different binary search tree ⅰ Leetcode 96

Verify binary search tree LeetCode 98

Restore binary search tree leetcode 99

Same tree as Leetcode 100

Symmetric binary tree LeetCode 101

The binary tree sequence traverses LeetCode 102

Binary tree zigzag sequence traversing Leetcode 103

The maximum depth of binary tree is LeetCode 104

Photograph taken