二叉树遍历

/**
 * 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 travel(curNode){
        // 先判断节点是否存在
        if(curNode === null) return
        result.push(curNode.val)
        // 依次递归左右节点
        if(curNode.left) travel(curNode.left)
        if(curNode.right) travel(curNode.right)
    }
    travel(root)
    return result
}

栈方法

var preOrderTraversal = function(root) {
    let result = []
    // 定义一个栈队列
    let task = []
    if(root) task.push(root)
    // 循环直到清空栈队列
    while(task.length>0){
        // 弹出栈顶节点
        let node = task.pop()
        result.push(node.val)
        node.right && task.push(node.right)
        node.left && task.push(node.left)
    }
    return result
};

二叉树中序遍历

将根节点放到中间处理，叫中序，先处理左节点，再处理左节点的父节点，最后处理右节点。

var inOrderTraversal = function(root) {
    let result = []
    // 定义一个遍历函数，用来将遍历的数放到结果队列中
    function travel(curNode){
        // 如果节点不存在直接返回
        if(curNode === null) return
        if(curNode.left)  travel(curNode.left)
        result.push(curNode.val)
        if(curNode.right) travel(curNode.right)
    }
    travel(root)
    return result
}

二叉树后序遍历

中间节点放最后处理

递归实现

var postOrderTraversal = function (root){
    let result = []
    function travel(curNode){
        if(curNode === null) return
        if(curNode.left) travel(curNode.left)
        if(curNode.right) travel(curNode.right)
        result.push(curNode.val)
    }
    travel(root)
    return result
}

遍历极简代码

此代码非常简单，但是考虑到面试官的理解能力，谨慎使用

总体思路就是一个动态规划，将问题分解为一个个子问题来处理：

var postOrderTraversal = function(root) {
    return root ? [...postOrderTraversal(root.left), ...postOrderTraversal(root.right), root.val] : []
};