二叉树的迭代、递归遍历

刷LeetCode刷到遍历二叉树的题目，前序（题号144，中等），中序（题号94，中等），后序（题号145，困难）。递归比较简单，但是题目建议可以用迭代，三道题用简单的递归也都可以通过，迭代的思路难一点。

JavaScript实现
前序-递归法：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
// 前序遍历，递归法
var preorderTraversal = function(root) {
    var res = [];
    res = getNode(root);
    return res;
};
var getNode = function(root){
    if(root === null){
        return [];
    }

    var arr = [];
    arr = [root.val].concat(getNode(root.left));
    arr = arr.concat(getNode(root.right));
    return arr;
};

前序-迭代法：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
// 前序遍历，迭代法
var preorderTraversal = function(root) {
    var cur = root;
    var res = [];
    var stack = [];
    while(cur || stack.length!==0){
        if(!cur){
            cur = stack.pop();
        }
        res.push(cur.val);
        if(cur.right){
            stack.push(cur.right);
        }
        cur = cur.left;
    }

    return res;
};

---

中序-递归法：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
// 题目要求用迭代，先写个递归看看
var inorderTraversal = function(root) {
    var res = [];
    res = getNode(root);
    return res;
};
var getNode = function(root){
    if(root === null){
        return [];
    }
    if(root.left===null && root.right===null){
        return [root.val];
    }
    var arr = [];
    // 左中右，中序遍历
    arr = getNode(root.left).concat([root.val]);
    arr = arr.concat(getNode(root.right));
    return arr;
};

中序-迭代法：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
// 迭代
var inorderTraversal = function(root) {
    if(root === null){
        return [];
    }
    var res = [];
    var stack = [];
    var cur = root;
    while(cur!==null || stack.length!==0){
        if(cur !== null){
            stack.push(cur);
            cur = cur.left;
        }else{
            cur = stack.pop();
            res.push(cur.val);
            cur = cur.right;
        }
    }
    return res;
};

---

后序-递归法：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    var res = [];
    res = getNode(root);
    return res;
};
var getNode = function(root){
    if(root === null){
        return [];
    }
    if(root.left===null && root.right===null){
        return [root.val];
    }
    var arr = [];
    arr = getNode(root.left).concat(getNode(root.right));
    arr = arr.concat([root.val]);
    return arr;
};

后序-迭代法：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
// 迭代
var postorderTraversal = function(root) {
    if(root === null){
        return [];
    }
    var res = [];
    var stack = [];
    var cur = root;
    while(cur || stack.length!==0){
        if(cur){
            stack.push(cur);
            cur = cur.left;
        }else{
            // 检查还有没有右边
            if(stack[stack.length-1].right){
                cur = stack[stack.length-1].right;
                stack[stack.length-1].right = null;
            }else{
                cur = stack.pop();
                res.push(cur.val);
                cur = null;
            }
        }
    }
    return res;
};

上面递归的方法其实没必要用两个function的，不过算了懒得改了。。看得明白就行