144. 二叉树的前序遍历
144. 二叉树的前序遍历
力扣题目链接[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/
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2022-04-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
