leetcode 144. Binary Tree Preorder Traversal(中等)

作者：okokabcd

2022 年 9 月 23 日
山东
本文字数：1024 字
阅读完需：约 3 分钟

leetcode 144. Binary Tree Preorder Traversal(中等)

一、题目大意

给你二叉树的根节点 root ，返回它节点值的前序遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

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

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/binary-tree-preorder-traversal著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、解题思路

二叉树的遍历，常见的有先序遍历、中序遍历、后序遍历和层序遍历，它们用 uxjv 实现起来都非常简单；

考虑使用非递归来实现，用到时 stack 来辅助转自，由于先序遍历的顺序为根左右，算法为：

1、把根节点 push 到栈中

2、循环检查栈是否为空，若不空，取出栈顶元素并保存其值，然后看其右节点是否存在，若存在则 push 到栈中，再看其左节点，若存在，则 push 到栈中

三、解题方法

3.1 Java 实现-递归

class Solution {    public List<Integer> preorderTraversal(TreeNode root) {        // 先序遍历：中左右        List<Integer> ans = new ArrayList<>();        preorder(root, ans);        return ans;    }
    void preorder(TreeNode node, List<Integer> ans) {        if (node == null) {            return;        }        ans.add(node.val);        preorder(node.left, ans);        preorder(node.right, ans);    }}

复制代码

3.2 Java 实现-迭代

public class Solution2 {    public List<Integer> preorderTraversal(TreeNode root) {        List<Integer> ans = new ArrayList<>();        if (root == null) {            return ans;        }        // 使用栈来辅助实现，Java中用双端队列来代替栈        Deque<TreeNode> stack = new ArrayDeque<>();        stack.addFirst(root);        while (!stack.isEmpty()) {            TreeNode tmp = stack.pop();            ans.add(tmp.val);            if (tmp.right != null) {                stack.addFirst(tmp.right);            }            if (tmp.left != null) {                stack.addFirst(tmp.left);            }        }        return ans;    }}

复制代码

四、总结小记

2022/9/23 遇到“上传下达”的情况，激情顿无，毫无意义

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/b31af0c3bc68c92c57996b45e】。文章转载请联系作者。

okokabcd

关注

还未添加个人签名 2019.11.15 加入

一年当十年用的Java程序员

发布

暂无评论

创作场景