leetcode144:二叉树的前序遍历
Opened this issue · 5 comments
sisterAn commented
给定一个二叉树,返回它的 前序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
附赠leetcode地址:leetcode
7777sea commented
var preorderTraversal = function(root) {
let stack = [root]
let arr = []
while (stack.length > 0) {
let node = stack.pop();
node && arr.push(node.val); // node不为空时,向arr中推入节点值
node && node.right && stack.push(node.right); // 模拟栈,所以先压右节点
node && node.left && stack.push(node.left); // 后入先出,后压左节点
}
return arr
};
plane-hjh commented
前序遍历
先访问根节点,再访问左节点,最后访问右节点。主要是看非递归版本的实现
递归实现
// 递归版本
const preOrderTraverse = (root) => {
let list = []
const preOrder = (node) => {
if(node !== null) {
// 先访问根节点
list.push(node.val)
// 再访问左节点
preOrder(node.left)
// 最后访问右节点
preOrder(node.right)
}
}
preOrder(root)
return list
}
非递归实现
// 非递归版本
const preOrderTraverseUnRecur = (root) => {
let list = [];
let stack = [root];
while(stack.length !== 0) {
const curNode = stack.pop()
const left = curNode.left
const right = curNode.right
// 第一步的时候,先访问的是根节点
list.push(curNode.val)
if(right) {
stack.push(right)
}
// 因为pop是取出最后一个元素,所以我们要确保首先拿到的是左节点
if(left) {
stack.push(left)
}
}
}
sisterAn commented
递归实现
// 前序遍历
var preorderTraversal = (root) => {
let result = []
var preOrderTraverseNode = (node) => {
if(node) {
// 先根节点
result.push(node.val)
// 然后遍历左子树
preOrderTraverseNode(node.left)
// 再遍历右子树
preOrderTraverseNode(node.right)
}
}
preOrderTraverseNode(root)
return result
};
迭代实现
利用栈来记录遍历的过程,实际上,递归就使用了调用栈,所以这里我们可以使用栈来模拟递归的过程
- 首先根入栈
- 将根节点出栈,将根节点值放入结果数组中
- 然后遍历左子树、右子树,因为栈是先入后出,所以,我们先右子树入栈,然后左子树入栈
- 继续出栈(左子树被出栈)…….
依次循环出栈遍历入栈,直到栈为空,遍历完成
// 前序遍历
const preorderTraversal = (root) => {
const list = [];
const stack = [];
// 当根节点不为空的时候,将根节点入栈
if(root) stack.push(root)
while(stack.length > 0) {
const curNode = stack.pop()
// 第一步的时候,先访问的是根节点
list.push(curNode.val)
// 我们先打印左子树,然后右子树
// 所以先加入栈的是右子树,然后左子树
if(curNode.right !== null) {
stack.push(curNode.right)
}
if(curNode.left !== null) {
stack.push(curNode.left)
}
}
return list
}
复杂度分析:
空间复杂度:O(n)
时间复杂度:O(n)
AnranS commented
var preorderTraversal = function (root) {
if (!root) return [];
let stack = [root];
let res = [];
while (stack.length) {
let node = stack.pop();
res.push(node.val);
if (node.right) {
stack.push(node.right);
}
if (node.left) {
stack.push(node.left);
}
}
return res;
};
kangkang123269 commented
非递归版
function preorderTraversal(root) {
if (!root) {
return [];
}
const stack = [root];
const result = [];
while (stack.length > 0) {
const node = stack.pop();
result.push(node.val);
// 先将右子树入栈,再将左子树入栈,保证先遍历左子树
if (node.right) {
stack.push(node.right);
}
if (node.left) {
stack.push(node.left);
}
}
return result;
}