题目：
94. Binary Tree Inorder Traversal(medium)
解题思路：
递归非常简单，迭代就是将递归的思想用栈实现。
统一前、中、后的迭代遍历方法
代码：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递归：
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inOrderHelper(root,res);
return res;
}
private void inOrderHelper(TreeNode root,List<Integer> list){
if(root != null){
if(root.left != null) inOrderHelper(root.left,list);
list.add(root.val);
if(root.right != null) inOrderHelper(root.right,list);
}
}
迭代：
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()){
while(cur != null ){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
res.add(cur.val);
cur = cur.right;
}
return res;
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if(root != null) stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.peek();
if(node != null){
stack.pop();//将该结点弹出，避免重复操作，下面再将右中左节点添加到栈中
if(node.right != null) stack.push(node.right);
stack.push(node);
stack.push(null);//中节点访问过，但还没有处理，需要做一下标记
if(node.left != null) stack.push(node.left);
}else{
stack.pop();//标记空结点弹出
node = stack.peek();//重新取出栈中元素
stack.pop();
res.add(node.val);
}
}
return res;
}
