leetcode144：二叉树的前序遍历

[sisterAn]

给定一个二叉树，返回它的 前序 遍历。

 示例:

输入: [1,null,2,3] 
 1
 \
 2
 /
 3 

输出: [1,2,3]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

附赠leetcode地址：leetcode

[7777sea]

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]

前序遍历

先访问根节点，再访问左节点，最后访问右节点。主要是看非递归版本的实现

递归实现

// 递归版本
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]

递归实现

// 前序遍历
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)

leetcode

[AnranS]

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]

非递归版

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;
}