Given a binary tree, return the inorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
\
2
/
3 Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?
法I：递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
if(root == null) return result;
inorder(root);
return result;
} public void inorder(TreeNode root) {
if(root.left!=null) inorder(root.left);
result.add(root.val);
if(root.right!=null) inorder(root.right);
} private List<Integer> result = new ArrayList<Integer>();
}
法II：循环。使用stack以及一个set标记当前节点是否访问过
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
Set<TreeNode> visitedSet = new HashSet<TreeNode>();//Set有HashSet和TreeSet两种实现
if(root == null) return result;
Stack<TreeNode> s = new Stack<TreeNode>();
TreeNode curNode = root;
while(true){
if(visitedSet.contains(curNode)){ //如果访问过，访问右儿子
result.add(curNode.val);
curNode = curNode.right;
} while(curNode!=null){ //如果没有访问过，自己先进栈，然后是左儿子
s.push(curNode);
visitedSet.add(curNode);
curNode = curNode.left;
}
if(s.empty()) break; //出栈一个节点
curNode = s.peek();
s.pop();
} return result;
}
}