友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
144. 二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
解释：
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[1,2,4,5,6,7,3,8,9]
解释：
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
提示：
-
树中节点数目在范围
[0, 100]内 -
-100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
思路分析
凡是用递归能解决的问题，都可以使用遍历来解决。用递归来求解问题，无非就是使用了方法栈来保存相关信息。同样，可以使用 Stack 来自己动手维护这些信息。
-
一刷
-
一刷（迭代）
-
二刷
-
三刷（Morris遍历）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Binary Tree Preorder Traversal.
* Memory Usage: 37.4 MB, less than 92.86% of Java online submissions for Binary Tree Preorder Traversal.
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-06-16 10:59
*/
public List<Integer> preorderTraversal(TreeNode root) {
if (Objects.isNull(root)) {
return Collections.emptyList();
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
List<Integer> result = new LinkedList<>();
while (!stack.empty()) {
TreeNode node = stack.pop();
result.add(node.val);
if (Objects.nonNull(node.right)) {
stack.push(node.right);
}
if (Objects.nonNull(node.left)) {
stack.push(node.left);
}
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-06-14 11:30
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
TreeNode head = root;
while (head != null || !stack.isEmpty()) {
if (head != null) {
result.add(head.val);
if (head.right != null) {
stack.push(head.right);
}
head = head.left;
} else {
head = stack.pop();
}
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-06-14 11:30
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
preorderTraversal(root, result);
return result;
}
private void preorderTraversal(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
result.add(root.val);
preorderTraversal(root.left, result);
preorderTraversal(root.right, result);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* 有一种巧妙的方法可以在线性时间内，只占用常数空间来实现前序遍历。
* 这种方法由 J. H. Morris 在 1979 年的论文「Traversing Binary Trees Simply and Cheaply」
* 中首次提出，因此被称为 Morris 遍历。
*
* @author D瓜哥 · https://www.diguage.com
* @since 2025-05-09 20:32:20
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
TreeNode cur = root;
TreeNode mostRight = null;
while (cur != null) {
mostRight = cur.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}
if (mostRight.right == null) {
result.add(cur.val);
mostRight.right = cur;
cur = cur.left;
continue;
} else {
mostRight.right = null;
}
} else {
result.add(cur.val);
}
cur = cur.right;
}
return result;
}