67.🌟Binary Tree Inorder Traversal

1.Description(Easy)

Given a binary tree, return the inorder traversal of its nodes' values.

Example

Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Challenge

Can you do it without recursion?

2.Code

先依次把left都压进栈中，再依次pop顺便遍历right,并再次把他们left全部压进栈中.

 public ArrayList<Integer> inorderTraversal(TreeNode root) {
       ArrayList<Integer> result=new ArrayList<Integer>();
         Stack<TreeNode> stack=new Stack<TreeNode>();
         TreeNode current=root;
         if(root==null){
             return result;
         }

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


         while(!stack.empty()){

             TreeNode top=stack.pop();
             result.add(top.val);
             if(top.right!=null){
                 top=top.right;

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

         }
         return result;
    }