题解 | #实现二叉树先序，中序和后序遍历#

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

/**
 * 
 * @param root TreeNode类 the root of binary tree
 * @return int整型二维数组
 */
function threeOrders( root ) {
    let middle = []  //用于存储三种结果
    let pre = []
    let last = []

    function preOrder (root){
        //先序
        if(!root){return null}   //判断是否到根节点
        pre.push(root.val)  //先保存根节点
        preOrder(root.left)  //递归遍历左节点
        preOrder(root.right)  //递归遍历右节点

    }
    function middleOrder (root){
        //中序
        if(!root){return null}
        middleOrder(root.left)  //递归遍历左节点
        middle.push(root.val)  //保存根节点
        middleOrder(root.right)   //递归遍历右节点

    }
    function lastOrder (root){
        //后序
        if(!root){return null}
        lastOrder(root.left)
        lastOrder(root.right)
        last.push(root.val)  //先左后右，最后储存根节点
    }

    //执行上面三个函数
    preOrder(root)
    middleOrder (root)
    lastOrder (root)

    //push到一个数组内
    let answer =[]
    answer.push(pre,middle,last)

    return answer

}
module.exports = {
    threeOrders : threeOrders
};

解题区内讲解

既然题目中提到二叉树先序，中序，后序遍历，那么我们就先聊一聊关于一个二叉树的先序，中序，后序遍历。遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有节点，使每一个节点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

二叉树的遍历主要有三种，括号内为其特点：

（1）先(根)序遍历（根左右）

（2）中(根)序遍历（左根右）

（3）后(根)序遍历（左右根）

图解