[Tree traversal]

Inorder: LinkedList<>stack=.. while ( root != null || !stack.isEmpty()) {        if ( root != null )       {             stack.push(root);             root = root.left;        }        else // root ==null       {             root= stack.pop();             res.add(root.val);             root= root.right;       } }

Preorder: LinkedList<>stack=.. while (root!= null || !stack.isEmpty()) {         if (root!= null)         {               stack.push(root);               res.add(root.val);              root =root.left;           }         else // root == null         {                root = stack.pop();                root = root.right;         } }

Postorder: LinkedList<>stack=... TreeNode pre = new TreeNode(); while (root != null || !stack.isEmpty()) {        if (root!= null)        {               stack.push(root);               root = root.left;        }        else // root ==null        {               TreeNode peekNode = stack.peek();               //while (peekNode.right != null && peekNode.right != pre)                              //peekNode.right == null;               if ( peekNode.right != null && pre != peekNode.right)               {                      root = peekNode.right;                }               else { //peekNode.right ==null                      stack.pop();                      res.add(pre.val);                      //root = pre.right;                      pre = peekNode;               }         } } peekNode.right != null, right has a chilren, traverse first 2. pre!= peekNode.right, already traverse right children, traverse me parent(root) now

public List<Integer> inorderTraversal (TreeNode root) {              List<Integer> res = new ArrayList<Integer>();              TreeNode cur = root;              TreeNode pre = null;              while (  cur != null )              { // root is NULL                       if (cur.left == null )                       {                                 res.add(root.val);                                 cur = cur.right;                        } // root is not NULL                       else                       {                                 pre = cur.left; // next level’s left                                 while (  pre.right != null && pre.right != cur  )                                        pre = pre.right;                                 if (   pre.right == null )                                 {                                           pre.right = cur;                                           cur = cur.left;                                 }                                  else                                 {                                           pre.right = null;                                          res.add(cur.val);                                           cur = cur.right;                                 }                        }              }              return res; }

Preorder Method3: Iterative, Morris, Time:O(n) ,Space:O(1) public List<Integer> preorder(TreeNode root){                    List<Integer> res = new ArrayList<Itneger>();        // validate the input        if (root == null)              return res;        TreeNode cur = root;        TreeNode pre = null;//your children        while (cur != null){                               if (  cur.left != null ){                          pre = cur.left;                         while( pre.right != null && pre.right != cur)                             pre = pre.right;                          if ( pre.right == null   ) // cur is root, so add                           {                                        res.add(cur.val);// case1: root, case2:left subtree last teo node                                         pre.right = cur;   // case1: root is left subtree’s right-most node’s children                                          cur =cur.left;                           }                           else                           {                                                 pre.right = null;  // case2: left -most right (originally is left subtree last two )asisgn null                                    cur = cur.right;// case2:cur =  left subtree last two node                            }                 }else { // cur is leaf, add                          res.add(root.val); //case4: the left-most node                         cur = cur.right;     //case4: its parent, left subtree’s last two                }       } }

PostoIrder MethodIter3:Iterative, Morris public List<Itneger>postorder(TreeNode root) {                 List<Integer> res=  new ArrayList<Integer>();                 //validate the input                 if ( root == null)                      return res;              TreeNode cur  = root;              TreeNode pre = null;              while (  cur != null  )              {                       if (  cur.left != null )                      {                      }              } }

public List<Integer> inorderTraversal(TreeNode root) {               List<Integer> res = new ArrayList<Integer>();                             // validate the input              if (root == null )                       return res;             helper(root, res);                      return res; } private void helper(TreeNode root, List<Integer> res) {           if (root == null)                return;           helper(root.left, res);           res.add(root.val);           helper(root.right, res); }

public List<Integer> preorder (TreeNode root){                     List<Integer> res = new ArrayList<Integer>();       // validate the input       if (root == null )           return res;            helper(root,res);      return res;        } private void helper(TreeNode root, List<Integer> res){             // Base case     if ( root == null )          return ;     res.add(root.val);     helper(root.left, res);     helper(root.right, res); }

public List<Itneger> postorder(TreeNode root) {            List<Integer> res=  new ArrayList<Intger>();         if (root == null)                return res;        helper(root, res);        } private void helper(TreeNode root, List<Itnger> res) {       // Base case       if (root == null)            return;       helper(root.left, res);       helper(root.right, res);      res.add(root.val); }