BiruLyu
7/26/2017 - 11:15 PM

## 144. Binary Tree Preorder 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> preorderTraversal(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; }
* }
*/

// eg:[10,5,30,-2,6,12,40,null,2,null,null,null,null,null,null,-1]
public class Solution {
public List<Integer> preorderTraversal(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> preorderTraversal(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;