题目
题目地址：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
给定一个二叉树，返回它的中序遍历。
示例:
1
2
3
4
5
6
7
8
| 输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
|
答案
使用栈实现（DFS）
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
| package com.jarome.leetcode.test1.inordertraversal;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.empty()) {
TreeNode peek = stack.peek();
if (peek.left != null) {
stack.push(peek.left);
peek.left = null;
continue;
}
stack.pop();
res.add(peek.val);
if (peek.right != null) {
stack.push(peek.right);
}
}
return res;
}
}
|
执行情况：
