Maybe the most direct method (Written by Java).


  • 1
    Z

    I use a pointer to mark the next node which should be added in the List. This simple method can prevent repeated traversal.

    1. Push the operating node and then its right child to the stack, then go left. Do this again and again until the operating node has no child.Make the pointer mark the next node whose value should be added in the List.
    2. Add the operating node's value to the List. Then pop the stack. If the node popped by the stack is the operating node's parent, then do this step again.If not, do the first step.

    public class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            List<Integer> ans = new ArrayList<Integer>();
            TreeNode p = root;
            TreeNode mark =root;
            while(p!=null||!stack.empty()){
                while(p!=null){
                    stack.push(p);
                    if(p.left!=null){
                        if(p.right!=null)
                            stack.push(p.right);
                        p=p.left;
                    }
                    else p=p.right;
                }
                p=stack.pop();
                mark=p;
                while(p==mark){
                    ans.add(p.val);
                    if(stack.empty()) return ans;
                    p=stack.pop();
                    if(p.left==mark||p.right==mark)
                        mark=p;
                }
            }
            return ans;
        }
    }

  • 0
    O

    Finally a solution with the same idea as mine! This doesn't need the reverse preorder hack and the sequence that each node is visited is truly postorder

    Sharing my C++ code with the same idea. Here the expand() function is to add the children of the the top node in the stack until it reaches the leave node. Then the top node of the stack is the one to be visited next.

    class Solution {
    public:
        void expand(stack<TreeNode *> & toVisit) {
            while (1) {
                TreeNode * cur = toVisit.top();
                if (cur->right) toVisit.push(cur->right);
                if (cur->left) toVisit.push(cur->left);
                if (!cur->left && !cur->right) break;
            }
        }
        vector<int> postorderTraversal(TreeNode* root) {
            stack<TreeNode *> toVisit, rootStack;
            vector<int> result;
            if (!root) return result;
            TreeNode * cur = root;
            toVisit.push(cur);
            expand(toVisit);
            while (!toVisit.empty()) {
                TreeNode * cur = toVisit.top();
                result.push_back(cur->val);
                toVisit.pop();
                if (toVisit.empty()) break;
                else {
                    if (!(cur == toVisit.top()->left || cur == toVisit.top()->right)) expand(toVisit);
                }
            }
            return result;
        }
    };
    

Log in to reply
 

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