144. 二叉树的前序遍历

思路

前序遍历也就是我们常用的深度遍历，解法很简单，不过莫里斯解法之前倒是没有接触过

递归

/**
 * 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 preorderTraversal(root: TreeNode | null): number[] {
    if (!root) return [];

    return [
        root.val,
        ...preorderTraversal(root.left),
        ...preorderTraversal(root.right)
    ];

};

栈

function preorderTraversal(root: TreeNode | null): number[] {
    let result = [];
    let stack = [root];

    let item: undefined | TreeNode;
    while((item = stack.pop())){
        result.push(item.val);
       
        item.right && stack.push(item.right);
        item.left && stack.push(item.left);
    }
    return result;
};

莫里斯

思路

代码

function preorderTraversal(root: TreeNode | null): number[] {
    const res:number[] = [];
    if (root == null) {
        return res;
    }

    let p1:TreeNode | null = root;
    let p2:TreeNode | null = null;

    while (p1 != null) {
        p2 = p1.left;
        if (p2 != null) {
            while (p2.right != null && p2.right != p1) {
                p2 = p2.right;
            }
            if (p2.right == null) {
                res.push(p1.val);
                p2.right = p1;
                p1 = p1.left;
                continue;
            }
            p2.right = null;
        } else {
            res.push(p1.val);
        }
        p1 = p1.right;
    }
    return res;
}