递归
解题思路
确定递归函数的参数和返回值；
确定终止条件；
确定单层递归的逻辑；
复杂度
-
时间复杂度：
O(n)，其中 n 是二叉树的节点数，每一个节点恰好被遍历一次； -
空间复杂度：
O(n)，为递归过程中栈的开销，平均情况下为O(logn)，最坏情况下树呈现链状，为O(n)；
代码实现
var preorderTraversal = function (root) {
const res = []; // 用于存储遍历的结果
preorder(root, res);
return res;
};
// 设置函数用于进行递归遍历
const preorder = (root, res) => {
if (root === null) return; // 当前结点为空时，无需进行递归
res.push(root.val); // 记录根节点值
preorder(root.left, res); // 前序遍历左子树
preorder(root.right, res); // 前序遍历右子树
}
迭代 + 栈
解题思路
先序遍历也叫 先根遍历 ，则遍历顺序为 根 -> 左 -> 右；
模拟递归的栈内存，首先访问根节点，然后将其入栈；
迭代栈：
- 出栈栈顶元素，放入结果中；
- 右节点不为空，右节点入栈；
- 左节点不为空，左节点入栈；
只要栈不为空，就会一直迭代下去，栈为空说明迭代结束；
图解
复杂度
-
时间复杂度：
O(n)，其中 n 是二叉树的节点数，每一个节点恰好被遍历一次； -
空间复杂度：
O(n)，为迭代过程中栈的开销，平均情况下为O(logn)，最坏情况下树呈现链状，为O(n)；
代码实现
var preorderTraversal = (root) => {
if (root === null) return [];
const stk = [root];
const res = [];
while (stk.length > 0) {
const node = stk.pop();
res.push(node.val);
if (node.right) stk.push(node.right);
if (node.left) stk.push(node.left);
}
return res;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 80. 删除有序数组中的重复项Ⅱ
上一篇
评论
