一、题目大意

给你二叉树的根节点 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

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

二、解题思路

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

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

1、把根节点push到栈中

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

三、解题方法3.1 Java实现-递归

class Solution {    public List preorderTraversal(TreeNode root) {        // 先序遍历：中左右        List ans = new ArrayList();        preorder(root, ans);        return ans;    }    void preorder(TreeNode node, List 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 preorderTraversal(TreeNode root) {        List ans = new ArrayList();        if (root == null) {            return ans;        }        // 使用栈来辅助实现，Java中用双端队列来代替栈        Deque 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 遇到“上传下达”的情况，激情顿无，毫无意义