Java solution with ONE Stack with explanation


  • 1
    G
    public class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            TreeNode vip = root;
            Stack<TreeNode> pending = new Stack<>();
            while(!(pending.isEmpty() && vip == null)) {
                while (vip != null) {
                    pending.push(vip);
                    vip = vip.left;
                }
                TreeNode temp = pending.pop();
                list.add(temp.val);
                vip = temp.right;
            }
            return list;
        }
    }
    

    As you can see, this solution only ONE stack plus an extra TreeNode pointer called vip which means you should push this to the stack immediately.


Log in to reply
 

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