一、题目粗心
给你二叉树的根节点 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/…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。
二、解题思路
二叉树的遍历，常见的有先序遍历、中序遍历、后序遍历和层序遍历，它们用 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 遇到“上传下达”的状况，激情顿无，毫无意义