【LeetCode】打家劫舍III

【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<stdio.h>#include<stdlib.h>// 定义二叉树的节点结构体structTreeNode{int val;structTreeNode*left;structTreeNode*right;};// 创建新的节点structTreeNode*newNode(int val){structTreeNode* node =(structTreeNode*)malloc(sizeof(structTreeNode)); node->val = val; node->left =NULL; node->right =NULL;return node;}// 辅助函数，计算打劫或不打劫当前节点能获得的最大金额inthelper(structTreeNode* root,int* robThisNode,int* notRobThisNode){if(root ==NULL){*robThisNode =0;*notRobThisNode =0;return0;}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);}// 主函数，计算打劫二叉树能获得的最大金额introb(structTreeNode* root){int robThisNode, notRobThisNode;returnhelper(root,&robThisNode,&notRobThisNode);}