BiruLyu
7/26/2017 - 11:18 PM

## 94. Binary Tree Inorder Traversal(Morris).java

``````/**
* 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) {

Deque<TreeNode> stack = new ArrayDeque<TreeNode>();

TreeNode cur = root;

while( cur != null || !stack.isEmpty()){

while(cur != null){
stack.push(cur);
cur = cur.left;
}

cur = stack.pop();
cur = cur.right;
}

return res;
}
}``````
``````/**
* 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) {

helper(root, res);
return res;
}

public void helper(TreeNode root, List<Integer> res){

if (root == null) return;
helper(root.left, res);
helper(root.right, res);
}
}``````
``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
// eg:[10,5,30,-2,6,12,40,null,2,null,null,null,null,null,null,-1]
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {

TreeNode cur = root;

while( cur != null){

if (cur.left == null) {
cur = cur.right;
} else {

TreeNode temp = cur.left;

while(temp.right != null && temp.right != cur){
temp = temp.right;
}

if (temp.right == null){
temp.right = cur;
cur = cur.left;
} else { // else if (temp.right == cur)
temp.right = null;
cur = cur.right;
}
}
}

return res;

}

}

/*
1.如果当前结点pNode的左孩子为空，那么输出该结点，并把该结点的右孩子作为当前结点；
2.如果当前结点pNode的左孩子非空，那么就找出该结点在中序遍历中的前驱结点pPre
2.1.当第一次访问该前驱结点pPre时，其右孩子必定为空，那么就将其右孩子设置为当前结点，以便根据这个指针返回到当前结点pNode中，并将当前结点pNode设置为其左孩子；
2.2.当该前驱结点pPre的右孩子为当前结点，那么就输出当前结点，并把前驱结点的右孩子设置为空（恢复树的结构），将当前结点更新为当前结点的右孩子

*/``````