友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
94. 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历。
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
提示：
-
树中节点数目在范围
[0, 100]内 -
-100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
思路分析
迭代的方式，还不是很理解，还需要再思考思考。
迭代的办法就是用栈来模拟递归：有左节点就入栈；没有左节点就出栈，然后把有节点再入栈；以此类推。注意，入栈左右子树节点时，要把上下级的关联给斩断，否则会造成死循环。
| 看官方题解，如果使用两层循环就不需要改变树的结构。自己想一想怎么实现？ |
“变形”莫里斯算法也是非常有趣：
| 详细介绍见： 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public List<Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> result = new LinkedList<>();
TreeNode head = root;
while (head != null || !stack.empty()) {
if (head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
result.add(head.val);
head = head.right;
}
}
return result;
}
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Binary Tree Inorder Traversal.
*
* Memory Usage: 34.8 MB, less than 100.00% of Java online submissions for Binary Tree Inorder Traversal.
*/
public List<Integer> inorderTraversal1(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
TreeNode current = root;
while (Objects.nonNull(current) || !stack.isEmpty()) {
while (Objects.nonNull(current)) {
stack.push(current);
current = current.left;
}
current = stack.pop();
result.add(current.val);
current = current.right;
}
return result;
}
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Binary Tree Inorder Traversal.
*
* Memory Usage: 34.7 MB, less than 100.00% of Java online submissions for Binary Tree Inorder Traversal.
*/
public List<Integer> inorderTraversalRecursion(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorderTraversal(root, result);
return result;
}
public void inorderTraversal(TreeNode root, List<Integer> result) {
if (Objects.isNull(root)) {
return;
}
inorderTraversal(root.left, result);
result.add(root.val);
inorderTraversal(root.right, 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> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorderTraversal(root, result);
return result;
}
public void inorderTraversal(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
inorderTraversal(root.left, result);
result.add(root.val);
inorderTraversal(root.right, result);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-06-14 11:30
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
TreeNode head = root;
while (head != null || !stack.isEmpty()) {
if (head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
result.add(head.val);
head = head.right;
}
}
return 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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-11-13 23:12:08
*/
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return Collections.emptyList();
}
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode peek = stack.peek();
if (peek.left != null) {
stack.push(peek.left);
peek.left = null;
} else {
TreeNode pop = stack.pop();
result.add(pop.val);
if (pop.right != null) {
stack.push(pop.right);
pop.right = null;
}
}
}
return result;
}