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

• ``````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;
}
};``````

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