C++ 16 ms iterative solution using post-order traversal


  • 0
    P
    class Solution {
    public:
    // Do a post-order traversal of the tree to compute max booty at each node from the bottom up
        int rob(TreeNode* root) {
            if (!root) return 0;
            stack<TreeNode*> stck;
            stck.push(root);
            TreeNode* prev = NULL;
            TreeNode* curr;
            while (!stck.empty()){
                curr = stck.top();
                // traversing down the tree
                if (!prev || prev->left==curr || prev->right==curr){
                    if (curr->left) stck.push(curr->left);
                    else if (curr->right) stck.push(curr->right);
                }
                // traversing up from the left
                else if (curr->left==prev){
                    if (curr->right) stck.push(curr->right);
                }
                // traversing up from the right, and other cases
                else {
                    int x1 = (curr->left ? curr->left->val : 0) + (curr->right ? curr->right->val : 0);
                    int x2 = curr->val + 
                             (curr->left && curr->left->left ? curr->left->left->val : 0) + 
                             (curr->left && curr->left->right ? curr->left->right->val : 0) + 
                             (curr->right && curr->right->left ? curr->right->left->val : 0) + 
                             (curr->right && curr->right->right ? curr->right->right->val : 0);
                    curr->val = max(x1, x2);
                    stck.pop();
                }
                prev = curr;
            }
            return root->val;
        }
    };

Log in to reply
 

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