BiruLyu
7/26/2017 - 11:19 PM

## 145. Binary Tree Postorder Traversal(Morris).java

``````/**
* 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> postorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
TreeNode cur = root;

while( cur != null || !stack.isEmpty()){
while(cur != null) {
stack.push(cur);
cur = cur.right;
}

cur = stack.pop();
cur = cur.left;

}

return 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> postorderTraversal(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> postorderTraversal(TreeNode root) {

TreeNode cur = new TreeNode(-1);
cur.left = 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 {
temp.right = null;
cur = cur.right;
}

}

}

return res;
}

public void reverseOrder(TreeNode start, TreeNode end){
if (start == end ) return;

TreeNode x = start;
TreeNode y = x.right;

while(true){
TreeNode temp = y.right;
y.right = x;
x = y;
y = temp;
if (x == end) break;
}

}
public void addReverseOrder(TreeNode cur, TreeNode pre, List<Integer> res){

reverseOrder(cur, pre);

TreeNode temp = pre;
while(true){
if(temp == cur) break;
temp = temp.right;
}

reverseOrder(pre,cur);
}
}

/*
1.先建立一个临时结点dummy，并令其左孩子为根结点root，将当前结点设置为dummy；
2.如果当前结点的左孩子为空，则将其右孩子作为当前结点；
3.如果当前结点的左孩子不为空，则找到其在中序遍历中的前驱结点
3.1如果前驱结点的右孩子为空，将它的右孩子设置为当前结点，将当前结点更新为当前结点的左孩子；
3.2如果前驱结点的右孩子为当前结点，倒序输出从当前结点的左孩子到该前驱结点这条路径上所有的结点。将前驱结点的右孩子设置为空，将当前结点更新为当前结点的右孩子。
4.重复以上过程，直到当前结点为空。
*/``````