Follow the process of post order, not reverse pre-order


  • 1
    Z
    public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> ans = new ArrayList<Integer>();
            Stack<TreeNode> stack = new Stack<TreeNode>();
           // Set<TreeNode> set = new HashSet<TreeNode>();
            
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            
            while(!stack.isEmpty()){
                TreeNode tmp = stack.peek();
                
                if(tmp.right == null){ // set.contains(tmp.right)
                    stack.pop();
                    ans.add(tmp.val);
                }
                else{
                    TreeNode cur = tmp;
                    tmp = tmp.right;
                    cur.right = null;
                   // set.add(tmp);
                    while(tmp != null){
                        stack.push(tmp);
                        tmp = tmp.left;
                    }
                }
            }   
            return ans;
        }
    

Log in to reply
 

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