方法一:递归
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> arraylist=new ArrayList<Integer>();
if(root==null){
return arraylist;
}
List<Integer> left=inorderTraversal(root.left);
List<Integer> right=inorderTraversal(root.right);
arraylist.addAll(left);
arraylist.add(root.val);
arraylist.addAll(right);
return arraylist;
}
}
方法二:迭代+栈
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> arraylist=new ArrayList<>();
if(root==null){
return arraylist;
}
//判断栈是否为空
Stack<TreeNode> stack=new Stack<TreeNode>();
TreeNode current=root;
while(current!=null||!stack.isEmpty()){
while(current!=null){
stack.push(current);
current=current.left;
}
current=stack.pop();
arraylist.add(current.val);
current=current.right;
}
return arraylist;
}
}