【LeetCode】打家劫舍III_java 打家劫舍3,需要先构建二叉树
【LeetCode】打家劫舍III
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
示例 1:
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
示例 2:
输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
提示：
树的节点数在 [1, 10^4] 范围内
0 <= Node.val <= 10^4
#include #include // 定义二叉树的节点结构体struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right;};// 创建新的节点struct TreeNode* newNode(int val) { struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode)); node->val = val; node->left = NULL; node->right = NULL; return node;}// 辅助函数，计算打劫或不打劫当前节点能获得的最大金额int helper(struct TreeNode* root, int* robThisNode, int* notRobThisNode) { if (root == NULL) { *robThisNode = 0; *notRobThisNode = 0; return 0; } int leftRob, leftNotRob; int rightRob, rightNotRob; // 递归计算左子树打劫和不打劫的最大金额 helper(root->left, &leftRob, &leftNotRob); // 递归计算右子树打劫和不打劫的最大金额 helper(root->right, &rightRob, &rightNotRob); // 如果打劫当前节点，则不能打劫左右子节点 *robThisNode = root->val + leftNotRob + rightNotRob; // 如果不打劫当前节点，则可以打劫或不打劫左右子节点，取最大值 *notRobThisNode = (leftRob > leftNotRob? leftRob : leftNotRob) + (rightRob > rightNotRob? rightRob : rightNotRob); // 返回两种情况的最大值 return (*robThisNode > *notRobThisNode? *robThisNode : *notRobThisNode);}// 主函数，计算打劫二叉树能获得的最大金额int rob(struct TreeNode* root) { int robThisNode, notRobThisNode; return helper(root, &robThisNode, ¬RobThisNode);}
