The key is to reversely add element~~


  • 4
    M

    The key to simply this problem is to always add number to the beginning of the list. Then postorder becomes very similar to preorder. (becomes head->right->left).

    public List<Integer> postorderTraversal(TreeNode root) {
    
    	List<Integer> ans = new LinkedList<Integer>();
    
    	if (root == null)
    		return ans;
    
    	Deque<TreeNode> stack = new LinkedList<TreeNode>();
    
    	stack.push(root);
    
    	while (!stack.isEmpty()) {
    		TreeNode current = stack.pop();
    		ans.add(0, current.val);
    		if (current.left != null)
    			stack.push(current.left);
    		if (current.right != null)
    			stack.push(current.right);
    	}
    
    	return ans;
    
    }

  • 0
    M

    Nice solution! But I'm curious about the time complexity. Especially in this statement "ans.add(0, current.val);" , does the time complexity could be O(n) for each adding?


  • 0
    M

    I think a adding an element to the beginning of a linked list should be O(1). But I don't know how Java implements this operation and whether it's acutully O(1).


Log in to reply
 

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