Concise iteration with single while loop in Java


  • 0
    B

    The logic is:

    1. Push and pop mainly work on root/curr node
    2. Every time push happens, let 'left' point to its left node
    3. Every time pop happens, push its right into the stack
    4. In each iteration, if 'left' is pointing a valid node, push the node; otherwise, it means left branch is done, so it can safely pop, collect the value, push the right in.
    public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<Integer>();
            if (root == null) return res;
            Deque<TreeNode> s = new LinkedList<TreeNode>();
            TreeNode curr;
            s.push(root);
            TreeNode left = root.left;
            
            while (!s.isEmpty()) {
                if (left != null) {
                    s.push(left);
                    left = left.left;
                } else {
                    curr = s.pop();
                    res.add(curr.val);
                    if (curr.right != null) {
                        s.push(curr.right);
                        left = curr.right.left;
                    }
                }
            }
            return res;
        }
    

Log in to reply
 

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