前言

因为疫情，辞职在家休息，打算先把驾照拿了，然后去广州，深圳，杭州这些地方去发展，可是计划赶不上变化，科二挂了，同时又因为疫情再约考又约不上，时间线被无情的拉长了，每天都很焦虑，到底是现在去这些大城市，还是继续呆长沙考驾照，亦或是在长沙找一份工作算了，尝试投了几份，可能是自己太菜了没找到合适的，也怪自己过去的2年工作像一个机器重复的搬砖没什么提高，待在长沙没什么目标感。现在改变现状，那就先改变自己开始, 比如在这段时间里面复习一遍数据结构和算法....

正文

我在开始之前看了这位大佬的bloglabuladong的算法小抄, 他的blog里面推荐优先刷树，它里面提的一个观点我比较认可， 数据结构服务于高效的完成数据的基本操作增删查改，而查(遍历)分为线性或非线性，线性就是for/while 迭代为代表，非线性就是递归为代表，大部分算法技巧，本质上都是树的遍历问题，这就是我为啥先选择刷二叉树。

什么是二叉树

树是一种具有层级关系的数据结构，树结构里面每个节点最多有2个子节点的树叫二叉树，两个子节点分别为左节点和有节点。学习二叉树可以获得以下技能，基本的递归思想，非线性数据结构遍历中的DFS(depth first search)深度遍历, BFS(Breadth first search)广度遍历，如何通过DFS或BFS的结果构建一个树等等。

深度遍历(DFS)

树的DFS又可以分为3种类型，分别是前序遍历(Pre-order Traversal)，中序遍历(In-order Traversal), 后序遍历(Post-order Traversal), 怎么区分这三种遍历呢？看下面这张图：

前序遍历(Pre-order Traversal): A->B->C，先访问父节点A

中序遍历(In-order Traversal): B->A->C, 先访问A的左子树，再访问A, 再访问A的右子树

后序遍历(Post-order Traversal): B->C->A 最后访问父节点A

练习树深度遍历可以使用递归的解决方法，如果使用迭代来实现树的递归，可以通过一个栈来模拟递归解决，DFS真的能很好的训练你的递归解决问题的能力，下面是leetcode上，前序，中序，后序最基础的练习题

注意！！！示例代码中树节点的统一定义:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
复制代码

前序遍历(Pre-order Traversal) leetcode链接

题目描述： Given a binary tree, return the preorder traversal of its nodes' values.

var preorderTraversal = function(root) {
    var res = [], stack = [root], tmpNode = null;
    while(stack.length !== 0){
        tmpNode = stack.pop()
        if(tmpNode){
            res.push(tmpNode.val)
            stack.push(tmpNode.right)
            stack.push(tmpNode.left)
        }
    }
    return res
};
复制代码

中序遍历(In-order Traversal) leetcode链接

题目描述： Given a binary tree, return the inorder traversal of its nodes' values.

// 别人优秀的代码：
const inorderTraversal = (root) => {
    let curr = root,  res = [], stack = [];
    while (curr || stack.length) {
        while (curr) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        res.push(curr.val);
        curr = curr.right;
    }
    return res;
};
// 我比较菜的代码:
var inorderTraversal = function(root) {
    var res = [], stack = [root], tmp = null, out = null;
    while(stack.length && root){
        tmp = stack[stack.length - 1]
        while(tmp.left && !tmp.left.out){
            stack.push(tmp.left)
            tmp = tmp.left
        }
        out = stack.pop()
        out.out = true
        res.push(out.val)
        if(out.right){
            stack.push(out.right)
        }
    }
    return res
};
复制代码

后序遍历(Post-order Traversal) leetcode链接

题目描述： Given a binary tree, return the postorder traversal of its nodes' values.

var postorderTraversal = function(root) {
    var res = [], curr = root, stack = [], last = null
    while(curr || stack.length){
        while(curr){
            stack.push(curr)
            curr = curr.left
        }
        curr = stack.pop()
        if(curr.right && last !== curr.right){
            stack.push(curr)
            curr = curr.right
        }else{
            res.push(curr.val)
            last = curr
            curr = null
        }   
    }
    return res
};
复制代码

广度遍历(BFS)

树的BFS可以概括为：先访问自己，再从左到右访问自己的子节点，上面一步完成后再从左到右访问自己的孙节点等等，这样一层层访问下去。树的广度遍历同时能既使用递归也能使用迭代，树的广度遍历使用递归可以理解为一种top-to-bottom的递归，top-to-bottom有点像树的先序遍历如下图(A)->(B->C)。 下面是树广度遍历的迭代版:

BFS leetcode链接

var levelOrder = function(root) {
    var res = [], queue = [root], tmp = []
    while(root && queue.length){
        tmp = queue
        queue = []
        res.push(tmp.map(tmpNode => {
            tmpNode.left && queue.push(tmpNode.left)
            tmpNode.right && queue.push(tmpNode.right)
            return tmpNode.val
        }))
    }
    return res
};
复制代码

构建树

一个树的构建既可以通过DFS遍历的结果构建，也可以通过BFS遍历的结果构建，下面分别介绍要如何构建

使用DFS遍历

使用DFS遍历的结果构建一颗二叉树需要两种遍历的结果，其中必须包含中序遍历的结果，因为在3种DFS遍历类型中，中序是唯一可以区分左子树集和右子树集，所以构建树可以使用中序+先序或中序+后序。

中序+先序leetcode链接

var buildTree = function(preorder, inorder) {
    var helper =(start, end) => {
        if(start > end) return null
        var val = preorder.shift(), 
            node = new TreeNode(val),
            index = inorder.indexOf(val)
        node.left = helper(start, index - 1)
        node.right = helper(index + 1, end)
        return node
    }
    if(preorder.length){
        return helper(0, preorder.length - 1)
    }
    return null
};
复制代码

中序+后序leetcode链接

var buildTree = function(inorder, postorder) {
    if(!inorder.length || !postorder.length) return null
    var fn = (li, ri,lp, rp) => {
        var centerVal = postorder[rp], index = inorder.indexOf(centerVal)
        if(li >= ri){
            var node = new TreeNode(inorder[li] || inorder[ri])
            return node
        }
        if(index !== -1){
            var node = new TreeNode(centerVal)
            node.left = index - li > 0 ? fn(li, index -1, lp, lp + index - 1 - li) : null
            node.right = ri - index > 0 ? fn(index + 1, ri,  lp + index - li , rp - 1) : null
        }
        return node
    }
    return fn(0, inorder.length - 1, 0, postorder.length -1 )
}
复制代码

使用BFS遍历

leetcode采用的就是BFS遍历的结果，进行序列化和反序列化构建树的，如图：

leetcode链接

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function(root) {
  var q1 = [root], q2 = [], res = []
  while(q1.length && root){
    q2 = []
    for(var i = 0; i < q1.length; i++){
        if(q1[i]){
            res.push(q1[i].val)
            q2.push(q1[i].left)
            q2.push(q1[i].right)
        }else{
            res.push(null)
        }
    }   
    q1 = q2  
  }
  while(res[res.length - 1] === null){
      res.pop()
  }  
  return JSON.stringify(res)
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
    data = JSON.parse(data)
    var root = null, queue = [], val;
    if(data.length){
        val = data.shift()
        root = new TreeNode(val)
        queue = [root]
    }
    while(data.length){
        while(queue.length){
            var l = data.shift()
            l = l !== void 0 ? l : null
            var r = data.shift() 
            r = r !== void 0 ? r : null
            val = queue.shift()
            if(l !== null){
                val.left = new TreeNode(l)
                queue.push(val.left)
            }
            if(r !== null){
                val.right = new TreeNode(r)
                queue.push(val.right)
            }
        }
    }
    return root
};

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */
复制代码

我刷的树练习题(持续更新中....)

Maximum Depth of Binary Tree

symmetric tree

path sum

populating next right pointers in each node

Lowest Common Ancestor of a Binary Tree

结语

我花了3天左右的时间重新学习了一遍二叉树，二叉树的主要知识点有：DFS,BFS, 树的构建(how to build binary tree)，至顶而下的递归(top to bottom recursion)，自下而上的递归(bottom to top resursion)这些知识点学完 后刷leetcode发现自己是真的菜，题目根本刷不动,而刷不动恰好说明有进步的空间，希望能通过刻意练习提高自己的算法能力，培养自己的计算机思维。