二叉树的中序遍历
题目介绍
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
示例 1：
示例 2：
示例 3：
示例 4：
示例 5：
提示：
- 树中节点数目在范围
[0, 100] 内
-100 <= Node.val <= 100
题目解法
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| package algorithm;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class BinaryTreeInorderTraversal {
static List<Integer> ans = new ArrayList<>();
public static List<Integer> inorderTraversal(TreeNode root) {
dfs(root);
return ans;
}
private static void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
ans.add(root.val);
dfs(root.right);
}
public static void main(String[] args) {
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
n1.left = null;
n1.right = n2;
TreeNode n3 = new TreeNode(3);
n2.left = n3;
System.out.println(Arrays.toString(inorderTraversal(n1).toArray()));
ans.clear();
TreeNode n4 = null;
System.out.println(Arrays.toString(inorderTraversal(n4).toArray()));
ans.clear();
TreeNode n5 = new TreeNode(1);
System.out.println(Arrays.toString(inorderTraversal(n5).toArray()));
ans.clear();
TreeNode n6 = new TreeNode(1);
TreeNode n7 = new TreeNode((2));
n6.left = n7;
System.out.println(Arrays.toString(inorderTraversal(n6).toArray()));
ans.clear();
TreeNode n8 = new TreeNode(1);
TreeNode n9 = new TreeNode(2);
n8.right = n9;
System.out.println(Arrays.toString(inorderTraversal(n8).toArray()));
ans.clear();
}
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
}
|
打印：
1
2
3
4
5
| [1, 3, 2]
[]
[1]
[2, 1]
[1, 2]
|
思路：
思路上，太简单了。我决定下次面试的时候，让候选者写一个。确实不难，而且也能判断这个人是否写过代码。