Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree [1,null,2,3],
1
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
在做99. Recover Binary Search Tree 时，要求不用O（n)的空间复杂度，只用constant space，因此不能用普通的迭代和递归法，递归里有函数栈，迭代里有用户声明的栈，都会带来Ｏ（lgn)-O(n)的空间复杂度。
用线索二叉树。
在迭代中，栈里存的都是根节点，是为了遍历完左子树后能重新找到根，再遍历根和右子树。想一种办法，能不用栈又能找回根节点。办法是：对每个根节点，首先找到在左子树里的它的前继节点，前继节点的right指针是闲置的，把闲置的right指针指向根，就可以重新找到根了。
什么时候恢复ｒｉｇｈｔ指针、并且在遍历这个根节点的时候如何知道，已经遍历过这个根节点的左子树，还是要开始遍历整个根下的树？
在一步步找根的前继节点时，如果找到right == root，说明之前已经重置过前继节点的ｒｉｇｈｔ指针了，这次应该恢复ｒｉｇｈｔ指针，并遍历ｒｏｏｔ的右子树;如果找到right == null,说明之前未遍历过root树，这次应当重置ｒｉｇｈｔ指针，并开始遍历ｒｏｏｔ的左子树。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
TreeNode cur = root, prev = null;
List<Integer> re = new LinkedList<Integer>();
while (cur != null) {
prev = cur.left;
if (prev == null) {
re.add(cur.val); // leaf node, traverse current node
cur = cur.right; // jump to its next
continue;
}
while (true) {
if (prev.right == null) {
prev.right = cur;
cur = cur.left;
break;
} else if (prev.right == cur) {
prev.right = null;
re.add(cur.val); // root node, traverse current node
cur = cur.right;
break;
}
prev = prev.right;
}
}
return re;
}
}
普通的迭代法:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> re = new LinkedList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode tmp = root, right;
while (tmp != null) {
stack.push(tmp);
tmp = tmp.left;
}
while (!stack.isEmpty()) {
tmp = stack.pop();
re.add(tmp.val);
right = tmp.right;
while (right != null) {
stack.push(right);
right = right.left;
}
}
return re;
}
}