Using only one stack and not the reverse of preorder (Java)


  • 1
    5

    By checking with the result list's last value, i can know if the tree node in the stack should be visited now or later.

    public class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> list=new ArrayList();
            if(root==null) return list;
            Stack<TreeNode> stack=new Stack();
            stack.push(root);
    
            while(!stack.isEmpty()){
                TreeNode t=stack.pop();
                TreeNode next=t.right!=null?t.right:t.left!=null?t.left:null;
    
                if(next!=null &&((list.size()==0)||(list.size()!=0 && list.get(list.size()-1)!=next.val))){
                    stack.push(t);
                    if(t.right!=null)stack.push(t.right);
                    if(t.left!=null) stack.push(t.left);
                }
                else{
                    list.add(t.val);
                }
            }
            return list;
        }
    }
    

  • 0
    A

    @531843133 The problem doesn't say all values are unique. You should not rely on the values.


Log in to reply
 

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