03统一的迭代遍历

3.统一的迭代遍历

前序遍历

题目

• 树中节点的数目在范围 [0, 100] 内

• 100 <= Node.val <= 100

思路

• 迭代法实现的先中后序，其实风格也不是那么统一，除了先序和后序，有关联，中序完全就是另一个风格了，一会用栈遍历，一会又用指针来遍历。

• 使用栈的话，无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。

• 那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。

Ts实现-中序遍历

function inorderTraversal(root: TreeNode | null): number[] {
    const stack: TreeNode[] = [];
    const res: number[] = [];
    let cur: TreeNode = null;
    if (root === null) return res;
    stack.push(root);
    while (stack.length > 0) {
        cur = stack.pop();
        // 左右中
        // 因为是栈，后进先出：中右左，其他代码改这里的顺序
        if (cur !== null) {
            if (cur.right !== null) stack.push(cur.right); // 右
            stack.push(cur);
            stack.push(null); // 中
            if (cur.left !== null) stack.push(cur.left); // 左
        } else {
            const inputStack = stack.pop();
            res.push(inputStack.val);
        }
    }
    return res;
};

Ts实现-前序遍历

function preorderTraversal(root: TreeNode | null): number[] {
    const stack: TreeNode[] = [];
    const res: number[] = [];
    let cur: TreeNode = null;
    if (root === null) return res;
    stack.push(root);
    while (stack.length > 0) {
        cur = stack.pop();
        // 左右中
        // 因为是栈，后进先出：中右左，其他代码改这里的顺序
        if (cur !== null) {
            if (cur.right !== null) stack.push(cur.right); // 右
            if (cur.left !== null) stack.push(cur.left); // 左
            stack.push(cur);
            stack.push(null); // 中
        } else {
            const inputStack = stack.pop();
            res.push(inputStack.val);
        }
    }
    return res;
};

Ts实现-后序遍历

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function postorderTraversal(root: TreeNode | null): number[] {
    const stack: TreeNode[] = [];
    const res: number[] = [];
    let cur: TreeNode = null;
    if (root === null) return res;
    stack.push(root);
    while (stack.length > 0) {
        cur = stack.pop();
        // 左右中
        // 因为是栈，后进先出：中右左，其他代码改这里的顺序
        if (cur !== null) {
            stack.push(cur);
            stack.push(null); // 中
            if (cur.right !== null) stack.push(cur.right); // 右
            if (cur.left !== null) stack.push(cur.left); // 左
        } else {
            const inputStack = stack.pop();
            res.push(inputStack.val);
        }
    }
    return res;
};