JavaScript算法套路之二叉树的前、中、后序递归遍历

Leetcode算法刷了那么多，是不是过了没多久就全忘记了，再遇到类似的题目，只能隐隐约约的记得曾经刷过，但依旧毫无思路。对，这是绝大多数人的通病，当然我也不例外，所以我潜心研究这到底是为什么，到底是为什么。终于找到了终结所在–光刷题，只是做了题，根本没有明白其内在原理，根本没有总结过做算法的套路。那么我就从二叉树的遍历开始，来总结一下相应的算法套路。

二叉树预备知识

     1
  /     \
  2       5
/   \      \
3    4       6

数据结构树的节点，最多有俩个子节点，就是二叉树。我是前端，那么前端的朋友一定会说，前端没有二叉树这种数据结构，如何表示呢？用数组,对，就是数组来表示，应该是这样的：

const tree = [1, 2, null, null, 5, 3, 4, null, 6];

二叉树的遍历

二叉树的遍历由深度优先和广度优先之分，那我们今天就先来说说深度优先，即：

• 前序遍历
• 中序遍历
• 后续遍历

那么你一定想知道这三种遍历有什么区别呢？对，共同点，都是从左枝叶开始遍历，那区别就是遍历中间节点点的位置在哪儿，我们来看下上面二叉树的遍历顺序：

//  前序遍历
1、2、3、4、5、6

//  中序遍历
3、2、4、1、5、6

//  后序遍历
3、4、2、6、5、1

所以我们就明白了。

总结套路

标题我们已经写过了，我们是用递归的方法来实现二叉树的遍历。那么我们要总结一下，如果写程序：

• 要确定参数是什么
  那二叉树的遍历，无论是前序遍历、中序遍历还是后续遍历，我们需要有树，要有节点，那么我们的参数就是节点喽。。。
• 终止条件是什么
  递归遍历，我们必须先想好终止的条件是什么。要不然就会造成栈溢出的情况对吧。那么对于二叉树来说，只要没有节点了，我们就改终止遍历了对吧，所以终止条件就是节点不存在。
• 单层递归的逻辑
  我们说了，二叉树前、中、后的遍历，是看根节点遍历的位置，所以这就是逻辑，对吧，是不是很简单。。。

代码实现

我们就照着以上总结的逻辑来用Javascript实现吧：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */

//  前序遍历 
var preOrderTraversal = function(root) {
    let result = [];
    function order (node) {
        if (!node) return;
        result.push(node.val);
        order(node.left);
        order(node.right);
    }
    order(root);
    return result;
};

//  中序遍历
var midOrderTraversal = function(root) {
    let result = [];
    function order (node) {
        if (!node) return;
        order(node.left);
        result.push(node.val);
        order(node.right);
    }
    order(root);
    return result;
};

//  后续遍历
var backOrderTraversal = function(root) {
    let result = [];
    function order (node) {
        if (!node) return;
        order(node.left);
        order(node.right);
        result.push(node.val);
    }
    order(root);
    return result;
};

是不是就发现很简答了，所以不要慌，要总结，才能学会。。。