Iterative simple java code 1ms using stack.


  • 0
    M
    public class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            // We need a stack to store the information regarding all the parent node paths.
            Stack<TreeNode> stack = new Stack<>();
            List<Integer> result = new ArrayList<>();
            if( root == null )
                return result;
            TreeNode curNode = root;
            boolean completed = false;
            while( !completed )
            {
                if( curNode != null )
                {
                    // Store the information of the parent nodes in an order.
                    stack.push(curNode);
                    curNode = curNode.left;
                }
                else 
                {   // If the stack is empty, it means that all the nodes are processed.
                    if( stack.isEmpty() )
                        completed = true;
                    else
                    {
                        // This makes sure that we process the node only when it's left sub-tree is fully processed.
                        curNode = stack.pop();
                        result.add(curNode.val);
                        // Now process the rigth sub-tree of the node. This ensures the Inorder traversal order LDR.
                        curNode = curNode.right;
                    }
                }
            }
            return result;
        }
    }
    

Log in to reply
 

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