二叉树的中序遍历。
中序遍历我记为 左 - 中- 右。
Inorder (Left, Root, Right) : 4 2 5 1 3
树的遍历大部分都是可以给出迭代和递归两种做法的，两种做法的时间和空间复杂度一样，时间都是O(n)，空间都是O(h)。
递归实现：
class Solution {
public List<Integer> inorderTraversal(TreeNode head) {
List<Integer> list=new ArrayList<>();
if(head==null){
return list;
}
process(head,list);
return list;
}
public void process(TreeNode node,List<Integer> list){
if(node==null){
return;
}
process(node.left,list);
list.add(node.val);
process(node.right,list);
}
}
非递归实现：
中：左中右
第一阶段：先遍历左子树入stack
第二阶段：弹出并打印cur，cur.right重复阶段一
class Solution {
public List<Integer> inorderTraversal(TreeNode head) {
if(head==null){
return new ArrayList<>();
}
List<Integer> result=new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur=head;
while (!stack.isEmpty()||cur!=null){
if(cur!=null){
stack.push(cur);
cur=cur.left;
}else {
cur=stack.pop();
result.add(cur.val);
cur=cur.right;
}
}
return result;
}
}