/*递归*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList<>();
if(root==null){
return list;
}
dfs(root,list);
return list;
}
private void dfs(TreeNode root,List<Integer> list){
if(root==null){
return;
}
dfs(root.left,list);
list.add(root.val);
dfs(root.right,list);
}
}
/*迭代*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
while(stack.size()>0 || root!=null) {
//不断往左子树方向走，每走一次就将当前节点保存到栈中
//这是模拟递归的调用
if(root!=null) {
stack.add(root);
root = root.left;
//当前节点为空，说明左边走到头了，从栈中弹出节点并保存
//然后转向右边节点，继续上面整个过程
} else {
TreeNode tmp = stack.pop();
res.add(tmp.val);
root = tmp.right;
}
}
return res;
}
}