踩坑日记 – “快乐”的二叉树（递归即栈）-一一网

作为一个叛逆的程序员，刷题竟然没有从二叉树开始，然后再去刷动态规划。

而是先刷的动态规划基础，觉得有点对不起labuladong的算法小抄的作者。

引子

刷题以来，最开始接触树是从斐波那契数列这类题目开始的。倒不是说树这个结构，而是树的思维。

斐波那契数列的递归解法

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

包利发完整的图就是一颗树，通过备忘录优化可以减少重复的运算

乃至可优化至只保存前两个状态即可

当时看到这个树的时候就觉得好哇塞，好像突然就觉得发现了世界的奥秘一样。于是遇到了很多题目练习，如N皇后，数独，就好像觉得递归，回溯，迭代啊傻傻的分不清，好像只要用一个套路，代码就能淡定的跑起来了。

也因此一直没有重视二叉树相关的问题，这几天强化了一下二叉树相关的体型，略有所得，但也还有一些纠结之处，在这里记录一下。

隐约的不安

最开始的纠结就是，递归到底是什么？为啥有很多问题我用递归就得心应手，但我一旦不用递归了，我就废了，就好像只会一种笨笨的套路，所有问题都只能这么“肤浅”的解决。

这个困扰了我半年多的疑惑，终于在今天的刷题之旅中，得到了解决。那就是递归即栈。也就是说，函数本身就是一种很高级的栈。高级到你一直都在使用，而没有察觉到他本质就是栈。

二叉树的中序遍历 leetcode 94

中序遍历递归左根右根在中间中序遍历

递归解法左、根、右略

迭代解法使用while循环 + 栈

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;
};
复制代码

今天的所有疑惑从这个迭代解法开始，就觉得隐约哪里不对劲，但是又说不上来。问题就是这个栈和我们的函数调用好像不太一样，不太一样的地方最开始我还说不上来，后来发现就是这个方案更优，他是这个中序遍历解法的一种特解，而不是传统的使用栈去模拟函数的递归调用。那如果是用栈模拟函数的递归调用呢？

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};
复制代码

这里核心的破局点在那里呢，在于对于函数作用域的模拟，栈的每一套push操作，都是在模拟函数的一次递归嵌套，每多一套push，就会多一层嵌套。每一套的pop操作都是在模拟函数的一次实际意义上的执行，每一套pop操作，就会多一次返回，少一层嵌套的函数。想通了这一点之后，在看题目给出的迭代答案，你不会觉得他是无中生有，而更多的是一种优化。不一定每一次你都能想象到最优解，但你逐步优化的过程会让你逐步靠近最优解。

今天的收获还有好多，但更多的是熟能生巧，刷到后面已经晕了，就感觉一道题目，不知道用什么方法更好，栈也能做，递归也能做，队列也能做，思维也逐渐变得僵硬了。下次有机会，我再来拜访一下二叉树

不同的二叉搜索树 Ⅱ leetcode 95

不同的二叉搜索树 Ⅰ leetcode 96

验证二叉搜索树 leetcode 98

恢复二叉搜索树 leetcode 99

相同的树 leetcode 100

对称二叉树 leetcode 101

二叉树的层序遍历 leetcode 102

二叉树的锯齿形层序遍历 leetcode 103

二叉树的最大深度 leetcode 104

合影留恋