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;
}
评论