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?
在一步步找根的前继节点时，如果找到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;
}
}
94. Binary Tree Inorder Traversal
原文：http://www.cnblogs.com/yuchenkit/p/7192193.html