二叉树的前序遍历|算法专题
# 题目
给定一个二叉树，返回它的 前序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]
@前端进阶之旅: 代码已经复制到剪贴板
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
# 代码
递归实现
var preorderTraversal = function (root, array = []) {
if (root) {
array.push(root.val);
preorderTraversal(root.left, array);
preorderTraversal(root.right, array);
}
return array;
};
@前端进阶之旅: 代码已经复制到剪贴板
非递归实现
- 取跟节点为目标节点，开始遍历
- 1.访问目标节点
- 2.左孩子入栈 -> 直至左孩子为空的节点
- 3.节点出栈，以右孩子为目标节点，再依次执行1、2、3
var preorderTraversal = function (root) {
const result = [];
const stack = [];
let current = root;
while (current || stack.length > 0) {
while (current) {
result.push(current.val);
stack.push(current);
current = current.left;
}
current = stack.pop();
current = current.right;
}
return result;
};
@前端进阶之旅: 代码已经复制到剪贴板
