Simple Java Iterative Solution, beats 40%


  • 2
    G

    Took a while to come up with this solution. It is short and takes Space = O(h) , where h is the height of the left tree. Runtime is O(n).

    public List<Integer> inorderTraversal(TreeNode root) {
    	List<Integer>result = new ArrayList<Integer>();
    	if (root == null)
    		return result;
    	Stack<TreeNode> stack = new Stack<TreeNode>();
    	TreeNode current = root;
            while(current!=null||!stack.isEmpty()){
                while(current!=null){
                    stack.push(current);
                    current=current.left;
                }
                current=stack.pop();
                result.add(current.val);
                current=current.right;
            }
            return result;
        }
    

Log in to reply
 

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