1ms stack based iterative solution


  • 0
    I
    public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            if(root == null) return list;
            ArrayDeque<TreeNode> stack = new ArrayDeque<>();
            TreeNode node = root;
            while (node != null){
                stack.push(node);
                node = node.left;
            }
            TreeNode lastNode = null;
            while (!stack.isEmpty()){
                TreeNode pop = stack.pop();
                if(lastNode == pop.left && pop.right != null){
                    // deal with right
                    stack.push(pop);
                    node = pop.right;
                    while (node!= null){
                        stack.push(node);
                        node = node.left;
                    }
    
                    lastNode = null;
                }
                else if(pop.right == null || lastNode == pop.right){
                    // deal with current
                    list.add(pop.val);
                    lastNode = pop;
                }
            }
            return list;
        }
    

Log in to reply
 

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