网站建设项目可行性报告,华为手机网络营销方式,下载小程序app,博客 wordpress题目描述#xff1a;给你二叉树的根节点 root #xff0c;返回它节点值的 前序 遍历。 输入#xff1a;root [1,null,2,3] * 输出#xff1a;[1,2,3] 解题思路#xff1a;
1 递归
2 迭代
前序 根左右
按照 根右左的顺序入栈#xff0c;因为先进后出
每个节点出栈的… 题目描述给你二叉树的根节点 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)
