我所认为的最好二叉树三序遍历

在此感谢 leetcode 网友提供的遍历方法

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/

二叉树的遍历是老生常谈的话题，递归方法最容易理解，但空间复杂度极高，由此衍生出了迭代遍历，但思维量巨大，每种遍历都需要写不同风格的代码。

我最近重写遍历时发现 网友 独创的遍历方式。

采用颜色标记法，未访问的用白色标记，访问的用黑色标记。

我们针对不同的遍历，只需要修改添加到数组时的顺序即可。

三种遍历方式代码风格极其相似，你还会怕写不出迭代遍历的代码吗？

前序遍历

var preorderTraversal = function(root) {
    let white = 0, black = 1
    let stack = [[white, root]]
    let result = []
    while(stack.length > 0) {
        let [color, node] = stack.pop()
        if(!node) continue
        if (color == white) {
            stack.push([white, node.right])
            stack.push([white, node.left])
            stack.push([black, node])
        }else{
            result.push(node.val)
        }
    }
    return result
};

中序遍历

var inorderTraversal = function(root) {
    let white = 0, black = 1
    let stack = [[white, root]]
    let result = []
    while(stack.length > 0) {
        let [color , node] = stack.pop()
        if (!node) {
            continue
        }
        if(color == white) {
            stack.push([white, node.right])
            stack.push([black, node])
            stack.push([white, node.left])
        }else{
            result.push(node.val)
        }
    }
    return result
};

后序遍历

var postorderTraversal = function(root) {
    let white = 0, black = 1
    let stack = [[white, root]]
    let result = []
    while(stack.length > 0) {
        let [color,node] = stack.pop()
        
        if (!node) continue
        if (color == white) {
            stack.push([black,node])
            stack.push([white, node.right])
            stack.push([white, node.left])
        }else {
            result.push(node.val)
        }
    }
    return result
};