提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

144. 二叉树的前序遍历

二叉树遍历 前序 144
2023-06-13 09:11:16 时间

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/

相关文章