4ms c++ solution


  • 0
    X

    1)It's the same to inorder traversal: use "nullptr" to help to move from left to right and from child to parent;

    1. use an anxiliary pointer "prev" to judge if right child has already been visited.
    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode *root) {
        vector<int> result;
    		stack<TreeNode*> s;
    		TreeNode *prev, *cur;
    		if (!root)
    			return result;
    		s.push(root);
    		while (!s.empty()) {
    			cur = s.top();
    			if (cur)
    				s.push(cur->left);
    			else {
    				s.pop();
    				if (!s.empty()) {
    					cur = s.top();
    					if (!cur->right || cur->right == prev) {
    						result.push_back(cur->val);
    						prev = cur;
    						s.pop();
    						s.push(nullptr);
    					} else
    						s.push(cur->right);
    				}
    			}
    		}
    		return result;
        }
    };

Log in to reply
 

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