337. 打家劫舍 III

树形DP。

1. DP数组的含义，这个已经不再是数组了，不过含义和之前相同
2. 遍历顺序，下面单独讲
3. 初始值，也不需要了
4. 打印DP数组，打印递归不是个明智的选择

得用递归，递归函数要求获取算当前节点和不算当前节点时最大的dp结果。
直接看代码吧，如果不选当前节点，不一定leftresult就一定得选择has，右节点同理；如果选了当前节点，左右就肯定得选nothas了

class result {
 public:
  int has_;
  int notHas_;
  result() : has_(0), notHas_(0) {}
  result(int has, int notHas) : has_(has), notHas_(notHas) {}
  int getMax()
  {
      return max(has_, notHas_);
  }
};

result treeRob(TreeNode *cur) {
  if (nullptr == cur) {
    return {0, 0};
  }

  auto leftResult = treeRob(cur->left);
  auto rightResult = treeRob(cur->right);

  result curResult;
  curResult.notHas_ = leftResult.getMax() + rightResult.getMax();
  curResult.has_ = cur->val + leftResult.notHas_ + rightResult.notHas_;
  return curResult;
}

int rob(TreeNode *root) {
  if (nullptr == root) {
    return 0;
  }
  auto ret = treeRob(root);
  return ret.getMax();
}