一、题目大意
给你二叉树的根节点 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 遇到“上传下达”的情况，激情顿无，毫无意义