二叉树的各种遍历

定义二叉树结点

class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

前序遍历

递归方法

function preorderTraversalRecursive(root) {
    if (root === null) return;
    console.log(root.value); // 访问根节点
    preorderTraversalRecursive(root.left); // 左子树
    preorderTraversalRecursive(root.right); // 右子树
}

迭代方法

function preorderTraversalIterative(root) {
    const stack = [root];
    while (stack.length > 0) {
        const node = stack.pop();
        console.log(node.value); // 访问节点
        if (node.right) stack.push(node.right); // 先右后左
        if (node.left) stack.push(node.left);
    }
}

中序遍历

递归方法

function inorderTraversalRecursive(root) {
    if (root === null) return;
    inorderTraversalRecursive(root.left); // 左子树
    console.log(root.value); // 访问根节点
    inorderTraversalRecursive(root.right); // 右子树
}

迭代方法

function inorderTraversalIterative(root) {
    const stack = [];
    let current = root;
    while (stack.length > 0 || current !== null) {
        while (current !== null) {
            stack.push(current);
            current = current.left; // 尽可能向左走
        }
        current = stack.pop();
        console.log(current.value); // 访问节点
        current = current.right;
    }
}

后序遍历

递归方法

function postorderTraversalRecursive(root) {
    if (root === null) return;
    postorderTraversalRecursive(root.left); // 左子树
    postorderTraversalRecursive(root.right); // 右子树
    console.log(root.value); // 访问根节点
}

迭代方法

• 双栈法

function postorderTraversalIterative(root) {
    if (!root) return;
    const stack1 = [root], stack2 = [];
    while (stack1.length) {
        const node = stack1.pop();
        stack2.push(node);
        if (node.left) stack1.push(node.left);
        if (node.right) stack1.push(node.right);
    }
    while (stack2.length) {
        console.log(stack2.pop().value); // 访问节点
    }
}

• 单栈法

function postorderTraversalIterativeSingleStack(root) {
    const stack = [];
    let current = root, prev = null;

    while (current || stack.length > 0) {
        if (current) {
            stack.push(current);
            current = current.left; // 尽可能向左走
        } else {
            const peekNode = stack[stack.length - 1];
            // 如果当前节点的右子节点存在且未被访问，则转向右子树
            if (peekNode.right && prev !== peekNode.right) {
                current = peekNode.right;
            } else {
                console.log(peekNode.value); // 访问节点
                stack.pop();
                prev = peekNode; // 更新prev为已访问的节点
            }
        }
    }
}