题目描述:给你二叉树的根节点 root ,返回它节点值的 前序 遍历。
输入:root = [1,null,2,3]
* 输出:[1,2,3]
解题思路:
1 递归
2 迭代
前序 根左右
按照 根右左的顺序入栈,因为先进后出
每个节点出栈的时候,记录节点的值,然后把他的左右节点入栈
解法一(递归):
const preOrder = (root) => {
const traverse = (curNode,res) => {
if(curNode === null) {
return;
}
res.push(curNode.value);
traverse(curNode.left,res);
traverse(curNode.right,res);
}
let res = [];
traverse(root);
return res;
}
用时:
// 35/35 cases passed (78 ms)
// Your runtime beats 70.69 % of typescript submissions
// Your memory usage beats 27.87 % of typescript submissions (55 MB)
解法二(迭代法(栈)):
const preOrder = (root) => {
if(root === null) {
return [];
}
let stack = [root];
let res = [];
let cur = root;
while(stack.length) {
// 根节点出栈
cur = stack.pop();
res.push(cur.val);
// 先进后出,右节点先入栈
if(cur.right) {
stack.push(cur.right);
}
if(cur.left) {
stack.push(cur.left);
}
}
return res;
}
用时:
// Your runtime beats 70.32 % of typescript submissions
// Your memory usage beats 47.95 % of typescript submissions (43.3 MB)