好久没有一把过了

本人语文水平不咋地，代码也写的不咋样

欢迎大家的评判与指正

总体思路：

自底向上的找出每个节点被打劫和不被打劫时，两种情况下的最大值

然后每个节点就可以根据自身的情况来找出，以当前节点为根节点时的最优解

当 当前节点被打劫时，两个子节点一定不会被打劫，则用当前节点的值+两个子节点都没有被打劫时的最大值

当 当前节点被打劫时，则两个子节点可能被打劫，也有可能不被打劫，所以就用0+左节点在两种情况下的最大值+右节点在两种情况下的最大值

static const auto io_sync_off = []() {
    // turn off sync
    std::ios::sync_with_stdio(false);
    // untie in/out streams
    std::cin.tie(nullptr);
    return nullptr;
}();
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型
     */



    int rob(TreeNode* root) {
        // write code here
        int answer = 0;
        if (!root) {
            return 0;
        } else if (nullptr == root->left && nullptr == root->right) {
            return root->val;
        }
        //  levelTree中的每一个元素都是一个map
        //      map的键为树中元素的位置(根节点位置为1，除根节点外任意左节点为其父节点的位置*2，任意右节点的位置为其父节点的位置*2+1)
        //      map的值为两个int
        //          第一个int为，以当前节点为根节点的树中，该节点不被"打劫"时的最大值
        //          第二个int为，以当前节点为根节点的树中，该节点被"打劫"时的最大值
        vector<map<int, pair<int, int>>> levelTree;
        // 下面两个deque是为了实现层次遍历
        deque<pair<int, TreeNode*>> q1;
        deque<pair<int, TreeNode*>> q2;
        q1.push_back({1, root});
        // level存放层次遍历中，同一行中的所有元素
        map<int, pair<int, int>> level;
        // 根节点的位置设置为1
        level.insert({1, {root->val, 0}});
        levelTree.push_back(level);
        // 将node节点声明在while外，是为了减少频繁声明局部变量而带来的消耗
        pair<int, TreeNode*> node = {0, nullptr};
        while (!q1.empty()) {
            level.clear();
            while (!q1.empty()) {
                node = q1.front();
                q1.pop_front();
                if (node.second->left) {
                    // 层次遍历时，得额外记一下节点的位置，要不然在遍历的时候，无法设定子节点的位置
                    q2.push_back({node.first * 2, node.second->left});
                    level.insert({node.first * 2, {node.second->left->val, 0}});
                }
                if (node.second->right) {
                    q2.push_back({node.first * 2 + 1, node.second->right});
                    level.insert({node.first * 2 + 1, {node.second->right->val, 0}});
                }
            }
            if (!level.empty()) {
                levelTree.push_back(level);
            }
            while (!q2.empty()) {
                node = q2.front();
                q2.pop_front();
                q1.push_back(node);
            }
        }
        // 不考虑只有一层的情况，只有一层的情况单独处理
        // rebegin时为了自底向上的遍历树节点
        // rbegin()+1是不想在最底层浪费时间
        // 因为最底层都是叶子节点，不可能有子节点
        // 其被打劫的情况下，得到的最大值就是当前节点
        // 其不被打劫时，得到的最大值就是0
        for (auto it = levelTree.rbegin() + 1; it != levelTree.rend(); it++) {
            // 由于使用rbegin，所以当前层的底下一层应该是it-1
            auto& nextLevel = *(it - 1);
            auto& curLevel = *it;
            for (auto i = curLevel.begin(); i != curLevel.end(); i++) {
                // 获取当前节点的左右节点，分别在两种情况(被打劫或不被打劫)下的最大值
                pair<int, int> left = {0, 0};
                pair<int, int> right = {0, 0};
                // 这里可以根据当前节点的位置，直接算出其两个子节点的位置，然后去下一层去找
                auto l = nextLevel.find((*i).first * 2);
                auto r = nextLevel.find((*i).first * 2 + 1);
                if (l != nextLevel.end()) {
                    left = (*l).second;
                }
                if (r != nextLevel.end()) {
                    right = (*r).second;
                }
                // 当前节点被打劫时，它的两个子节点必定不会被打劫
                (*i).second.first += left.second + right.second;
                // 当前节点不被打劫时，则分别取其两个节点在两种情况中更大的值
                (*i).second.second += max(left.first, left.second) + max(right.first,
                                      right.second);
            }
        }
        answer = max((*(levelTree[0].begin())).second.first,
                     (*(levelTree[0].begin())).second.second);
        return answer;
    }

};