力扣题目链接[1]
给你二叉树的根节点 root
,返回它节点值的「前序」遍历。
示例一:
输入:root = [1,null,2,3]
输出:[1,2,3]
「提示:」
[0, 100]
内100 <= Node.val <= 100
进阶:递归算法很简单,你可以通过迭代算法完成吗?
思路:
二叉树的遍历分为前序、中序、后序遍历。这里先解决前序遍历。
先使用递归来求解。前序遍历的顺序是根左右,因此先将当前节点的值放入结果数组中,然后再递归的求出左节点和右节点即可。
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
let result = [];
const preOrder = (root) => {
if (!root) return;
result.push(root.val);
preOrder(root.left);
preOrder(root.right);
}
preOrder(root);
return result;
};
递归的本质就是调用栈,因此可以使用栈来实现迭代式的前序遍历。
核心思路是:首先将根节点放入栈中,方便后续判断。当栈内有元素就持续循环,每次循环都将栈顶元素弹出,直接放入结果数组中,相当于先遍历了根节点。因为栈的特点是后进先出,所以我们要先将右子节点放入栈中,再将左子节点放入栈中。这样弹出的顺序才是左子节点和右子节点。
由此,达到了前序遍历的目的。
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
let result = [];
let stack = [];
if (root) stack.push(root);
while(stack.length) {
const root = stack.pop();
result.push(root.val);
if (root.right) stack.push(root.right);
if (root.left) stack.push(root.left);
}
return result;
};
这里分别采用了递归和迭代的方式来实现前序遍历。递归的思路很好理解,这里需要重点掌握迭代的方式。而迭代的核心思想跟递归是类似的,因为递归就是调用栈。因此迭代是采用了栈来实现前序遍历。由于栈的特点是后进先出,因此需要注意放入左右子节点的顺序,保证弹出顺序是正确的。
[1]
力扣题目链接: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/