二叉树算法题

学到的解题方法

前序遍历(LeetCode 144)

leetcode

前序遍历，迭代1

var preorderTraversal = function(root) {
    let result = [],stack = [],p = root
    while(p) {
        result.push(p.val)
        if(p.left && p.right) {
            stack.push(p.right)
            p = p.left
        } else if(p.left) {
            p = p.left
        } else if(p.right) {
            p = p.right
        } else {
            p = stack.pop()
        }
    }
    return result
}

前序遍历，迭代2

var preorderTraversal = function(root) {
    const stack = [root],ret = []
    let p
    while(p = stack.pop()) {
        ret.push(p.val)
        if(p.right) { stack.push(p.right) }
        if(p.left) { stack.push(p.left) }
    }
    return ret
}

后序遍历(LeetCode 145)

leetcode

后序遍历，迭代1

var postorderTraversal = function(root) {
    let result = [],stack = [],p = root
    while(p || stack.length) {
        while(p) { // 先找到最左下的节点,从下往上输出
            stack.push(p)
            p = p.left
        }
        p = stack.pop()
        let prev = null // 回溯标记,如果是回溯回来的才输出当前点
        if(!p.right || p.right === prev) { // 如果p右节点为空,或者是从右节点回溯回来的,就输出当前点
            result.push(p.val)
            prev = p
            p = null
        } else { // 如果存在右节点,且当前不是回溯回来的,则得先输出右子树
            stack.push(p)
            p = p.right
        }
    }
    return result
};

后序遍历，迭代2(前序遍历翻转)

var postorderTraversal = function(root) {
    const stack = [root],ret = []
    let p
    while(p = stack.pop()) {
        ret.unshift(p.val)
        if(p.left) { stack.push(p.left) }
        if(p.right) { stack.push(p.right) }
    }
    return ret
};