LeetCode-337 House Robber III
题目描述
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.
题目大意
给定一棵二叉树，不能同时选择相邻结点的数值，求可能得到的结点值之和的最大值。
示例
E1
Input: [3,2,3,null,3,null,1]3/ \2 3\ \ 3 1 Output: 7 Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.E2
Input: [3,4,5,1,3,null,1]3/ \4 5/ \ \ 1 3 1Output: 9 Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
解题思路
递归遍历，计算当前结点以及其孙子结点的数值之和，和该结点的两个孩子结点之和进行比较，返回较大值。
复杂度分析
时间复杂度：O(N)
空间复杂度：O(N)
代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:int rob(TreeNode* root) {int l = 0, r = 0;return dfs(root, l, r);}int dfs(TreeNode* root, int& l, int& r) {if(root == NULL)return 0;int ll = 0, lr = 0, rl = 0, rr = 0;l = dfs(root->left, ll, lr);r = dfs(root->right, rl, rr);return max(root->val + ll + lr + rl + rr, l + r);} };
转载于:https://www.cnblogs.com/heyn1/p/11212240.html
总结
以上是生活随笔为你收集整理的LeetCode-337 House Robber III的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： 关于Linux服务器配置java环境遇到
- 下一篇： 列表，集合，元组，字典