Java simple and clean


  • 51
    J
    public List<Integer> postorderTraversal(TreeNode root) {
    	LinkedList<Integer> ans = new LinkedList<>();
    	Stack<TreeNode> stack = new Stack<>();
    	if (root == null) return ans;
    	
    	stack.push(root);
    	while (!stack.isEmpty()) {
    		TreeNode cur = stack.pop();
    		ans.addFirst(cur.val);
    		if (cur.left != null) {
    			stack.push(cur.left);
    		}
    		if (cur.right != null) {
    			stack.push(cur.right);
    		} 
    	}
    	return ans;
    }

  • 2
    M

    Brilliant code, I think it's faster than usual iterative solution. Every time it gets in while loop, it can pop one out and push two in if possible. The most smart trick is to add value from last, which saves a Hash Set to record visited nodes.


  • 0
    Y

    brilliant solution, also inspired mine. I used to have a hash set


  • 0
    S

    Many thanks.


  • 0
    H
    This post is deleted!

  • 0
    H

    Here's my clean recursive solution:

    public class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> res = new LinkedList<>();
            helper(res, root);
            return res;
        }
        public void helper(List<Integer> list, TreeNode root){
            if(root == null)    return;
            helper(list, root.left);
            helper(list, root.right);
            list.add(root.val);
        }
    }
    

  • 0
    T

    The code returns a list like "root-right-left", why can we code like this when the question asks us to return Postorder Traversal "left-right-root"?


  • 0
    H

    @twopipi here we use list.addFirst, which add element to the left most node. This is like add(0,item).


  • 0
    T

    @hfu I get it. Thanks very much.


  • 0
    F

    @twopipi he used LinkedList.addFirst(), it's like using a stack


Log in to reply
 

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