Postorder Traversal Java solution both recursion and iteration


  • 3
    K
    // recursive
    public class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> result = new ArrayList<Integer>();
            if (root == null) return result;
            postordtree(result, root);
            return result;
        }
        private void postordtree(List<Integer> result, TreeNode node){
            if (node.left != null) postordtree(result, node.left);
            if (node.right != null) postordtree(result, node.right);
            result.add(node.val);
        }
    }
    
    // iterative
    public class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            // https://en.wikipedia.org/wiki/Tree_traversal
            // iterative
            List<Integer> result = new ArrayList<Integer>();
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode last = null;
            TreeNode peeknode = null;
            while (!stack.isEmpty() || root != null){
                if (root != null){
                    stack.push(root);
                    root = root.left;
                    // traverse to the leftmost
                }
                else{
                    peeknode = stack.peek();
                    if(peeknode.right != null && last != peeknode.right) root = peeknode.right;
                    else{
                        result.add(peeknode.val);
                        last = stack.pop();
                    }
                }
            }
            return result;
        }
    }

Log in to reply
 

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