二叉树的前中后序遍历

二叉树如上图
前中后序遍历其实就是说的中间节点位置
前序遍历：中，左，右
中序遍历：左，中，右
后序遍历：左，右，中

递归实现如下：

// 定义二叉树的节点
class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

const res = [];// 存储遍历结果

// 前序遍历
function preOrderTraversal(node) {
    if (node !== null) {
        // console.log(node.value);
        res.push(node.value);
        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
    }
}

// 中序遍历
function inOrderTraversal(node) {
    if (node !== null) {
        inOrderTraversal(node.left);
        // console.log(node.value);
        res.push(node.value);
        inOrderTraversal(node.right);
    }
}

// 后序遍历
function postOrderTraversal(node) {
    if (node !== null) {
        postOrderTraversal(node.left);
        postOrderTraversal(node.right);
        // console.log(node.value);
        res.push(node.value);
    }
}


// 使用示例
const tree = new TreeNode(1);
tree.left = new TreeNode(2);
tree.right = new TreeNode(3);
tree.left.left = new TreeNode(4);
tree.left.right = new TreeNode(5);
tree.right.left = new TreeNode(6);

console.log('前序遍历:');
preOrderTraversal(tree);
console.log(res);
res.length = 0;// 清空数组

console.log('中序遍历:');
inOrderTraversal(tree);
console.log(res);
res.length = 0;// 清空数组

console.log('后序遍历:');
postOrderTraversal(tree);
console.log(res);
res.length = 0;// 清空数组

依次的递归访问左右节点 但是前序遍历就在访问左右节点前打印，中序遍历在访问左节点后，后序遍历在访问完左右节点后打印。
打印如下：

前序遍历:
(6) [1, 2, 4, 5, 3, 6]
中序遍历:
(6) [4, 2, 5, 1, 6, 3]
后序遍历:
(6) [4, 5, 2, 6, 3, 1]

用栈的方式实现：

// 定义二叉树的节点
class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

/**
 * @description 使用带有访问标志的栈来模拟递归 前序遍历
 * @param {TreeNode} root
 * @return {number[]}
 */
var preOrderTraversal = function (root) {
    const [WHITE, GRAY] = [0, 1]; // WHITE - 未访问的新结点； GRAY - 已访问的结点
    const res = [];
    const stack = [[WHITE, root]];
    let color, node;
    while (stack.length) {
        [color, node] = stack.pop();
        if (!node) continue;
        if (color === WHITE) {
            stack.push([WHITE, node.right]);
            stack.push([WHITE, node.left]);
            stack.push([GRAY, node]);
        } else res.push(node.value);
    }
    return res;
};


/**
 * @description 使用带有访问标志的栈来模拟递归 中序遍历
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
    const [WHITE, GRAY] = [0, 1]; // WHITE - 未访问的新结点； GRAY - 已访问的结点
    const res = [];
    const stack = [[WHITE, root]];
    let color, node;
    while (stack.length) {
        [color, node] = stack.pop(); // 若栈中有元素，则按照左节点、根节点、右节点的顺序依次弹出元素
        if (!node) continue;
        if (color === WHITE) {
            // 当前指向的结点是未访问过的结点，将其右节点，根节点，左节点依次入栈
            stack.push([WHITE, node.right]);
            stack.push([GRAY, node]);
            stack.push([WHITE, node.left]);
        } else res.push(node.value);
    }
    return res;
};

/**
 * @description 使用带有访问标志的栈来模拟递归 后序遍历
 * @param {TreeNode} root
 * @return {number[]}
 */
var postOrderTraversal = function (root) {
    const [WHITE, GRAY] = [0, 1]; // WHITE - 未访问的新结点； GRAY - 已访问的结点
    const res = [];
    const stack = [[WHITE, root]];
    let color, node;
    while (stack.length) {
        [color, node] = stack.pop();
        if (!node) continue;
        if (color === WHITE) {
            stack.push([GRAY, node]);
            stack.push([WHITE, node.right]);
            stack.push([WHITE, node.left]);
        } else res.push(node.value);
    }
    return res;
};


// 使用示例
const tree = new TreeNode(1);
tree.left = new TreeNode(2);
tree.right = new TreeNode(3);
tree.left.left = new TreeNode(4);
tree.left.right = new TreeNode(5);
tree.right.left = new TreeNode(6);

console.log('前序遍历:');
console.log(preOrderTraversal(tree));

console.log('中序遍历:');
console.log(inorderTraversal(tree));

console.log('后序遍历:');
console.log(postOrderTraversal(tree));

打印如下：

前序遍历:
(6) [1, 2, 4, 5, 3, 6]
中序遍历:
(6) [4, 2, 5, 1, 6, 3]
后序遍历:
(6) [4, 5, 2, 6, 3, 1]

也是只需要修改入栈顺序即可 因为栈是先入后出 所以入栈顺序和出栈顺序相反。
参考链接：
https://leetcode.cn/problems/binary-tree-inorder-traversal/solutions/412886/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/

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