遍历二叉树

总结了二叉树的先序、中序、后序遍历算法，分别给出了这三种算法的递归写法和迭代写法。
默认数据结构如下：

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

先序

中左右  

/**
 * Recursive 递归
 * 纯函数
 */
var preorderTraversal = function(root) {
    var r = [];

    if(!root) return [];

    r.push(root.val);

    if(root.left)
        r = r.concat(preorderTraversal(root.left));

    if(root.right)
        r = r.concat(preorderTraversal(root.right));

    return r;
};

/**
 * iteratively 迭代
 * 思路：首先把根节点入栈，然后迭代以下过程:
 * 出栈，输出这个节点，这个节点的右、左子节点依次入栈
 */

var preorderTraversal = function(root) {
    const stack = [];

    stack.push(root);

    const traversal = [];

    while (stack.length){
        const node = stack.pop();

        if (!node){
            continue;
        }

        traversal.push(node.val);

        stack.push(node.right);
        stack.push(node.left);
    }

    return traversal;
};

中序

左中右  

/**
 * Recursive 递归
 */
var inorderTraversal = function(root) {
    var r = [];

    if(!root) return [];

    if(root.left)
        r = r.concat(inorderTraversal(root.left));

    r.push(root.val);

    if(root.right)
        r = r.concat(inorderTraversal(root.right));

    return r;
};

/*
 * iteratively 迭代
 */
var inorderTraversal = function(root) {
    let result = [];
    let stack = [];
    let node = root;

    while(stack.length > 0 || node !== null) {
        while(node) {
            stack.push(node);
            node = node.left;
        }

        if (stack.length !== 0) {
            node = Stack.pop();
            result.push(node.val);
            node = node.right;
        }
    }

    return result;
};

/**
 * iteratively 迭代
 * 思路：首先把根节点入栈，然后迭代以下过程:
 * 1.出栈
 * 2.如果这个节点的子节点没有被Push进栈过(判断方法不写了)，依次push右子节点、这个节点、左子节点。
 * 3.判断是否pop并输出。判断方法：leftChild == null || letfChild == 上一次输出的节点 || 上一次输出的节点的rightChild == null 
 */
var inorderTraversal = function(root) {
    const stack = [];
    const traversal = [];
    let lastOut;
    let thisNode;

    stack.push(root);

    while (stack.length){

        // 1
        thisNode = stack.pop();

        if(thisNode == null) {
            continue;
        }
        // 2
        if (thisNode.right != null && !(lastOut != null && lastOut == thisNode.left) && !(lastOut != null && lastOut.right == null)) {
            stack.push(thisNode.right);
        }

        stack.push(thisNode);

        if (thisNode.left != null && !(lastOut != null && lastOut == thisNode.left) && !(lastOut != null && lastOut.right == null)) {
            stack.push(thisNode.left);
        }

        // 3
        // thisNode = stack[stack.length - 1];
        if( thisNode.left == null || thisNode.left == lastOut || (lastOut && lastOut.right == null)) {
            lastOut = stack.pop();
            traversal.push(lastOut.val);
        }
    }

    return traversal;
};

后序

左右中  

/**
 * Recursive 递归
 */
 var postorderTraversal = function(root) {
    var r = [];

    if(!root) return [];

    if(root.left)
        r = r.concat(postorderTraversal(root.left));

    if(root.right)
        r = r.concat(postorderTraversal(root.right));

    r.push(root.val);
    return r;
};

/**
 * Recursive 递归2
 */
var postorderTraversal = function(root) {
    let result = [];
    helper(result, root);

    return result;
};

var helper = function(r, root) {
    if(root != null) {
        helper(r, root.left);
        helper(r, root.right);
        r.push(root.val);
    }
}

/**
 * iteratively 迭代
 */
var postorderTraversal = function(root) {
    var treeNodeStack = [];
    var node = root;
    var lastVisit = root;
    var res = [];
    while (node != null || treeNodeStack.length>0) {
        while (node != null) {
            treeNodeStack.push(node);
            node = node.left;
        }

        node = treeNodeStack[treeNodeStack.length-1];

        if (node.right == null || node.right == lastVisit) {
            res.push(node.val);
            treeNodeStack.pop();
            lastVisit = node;
            node = null;
        } else {
            node = node.right;
        }
    }

    return res;
};