Binary Tree Inorder Traversal
Solution 1: recursive
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
inorder(root, res);
return res;
}
private void inorder(TreeNode root, List<Integer> res){
if (root==null) return;
inorder(root.left, res);
res.add(root.val);
inorder(root.right, res);
}
}
Solution 2: iterative
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> res = new ArrayList<Integer>();
TreeNode cur= root;
while(cur!=null || !stack.isEmpty()){
while(cur!=null){
stack.add(cur);
cur = cur.left;
}
cur = stack.peek();
stack.pop();
res.add(cur.val);
cur = cur.right;
}
return res;
}
}