My java solution uses the Stack to simulate the recursive.


  • 2
    J
    public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
         List<Integer> result = new java.util.ArrayList<Integer>();
         inorder(root,result);
         return result;
    }
    
    private void inorder(TreeNode root,List<Integer> result){
       java.util.Stack<TreeNode> stack = new java.util.Stack<TreeNode>();
       if(root==null) return;
       if(root.right!=null) stack.push(root.right);
       stack.push(root);
       if(root.left!=null) stack.push(root.left);
       root.left = null;
       root.right = null;
       while(!stack.empty()){
           TreeNode temp = stack.pop();
           if(temp.left==null&&temp.right==null){
               result.add(temp.val);
           }else{
               if(temp.right!=null) stack.push(temp.right);
               stack.push(temp);
               if(temp.left!=null) stack.push(temp.left);
               temp.left = null;
               temp.right = null;
           }
       }
    }
    

    }

    The solution is very simple.Just add the node to the stack,first left node,then node self and last right node.After the node self to pushed into stack ,its left node and right node should be set to null to represent the node could just be read value.Then just pop every node in stack,if the node has left node or right node just dispose it to the same as before,otherwise just add the it value in result.


  • 0
    G

    Hi! IMO: Altering the TreeNode is a bit ugly, some interviewers might not let you pass that...


  • 0
    J

    Thanks.Altering the content of TreeNode is't actually a good method.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.