当前位置：网站首页>LeetCode-337. House Robber III

LeetCode-337. House Robber III

2022-08-10 15:35:00 【51CTO】

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.

Example 1:

       
       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.
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.

Example 2:

       
       Input: [3,4,5,1,3,null,1]
       
     3
       
    / \
       
   4   5
       
  / \   \ 
       
 1   3   1
       
Output: 9
       
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.

题解：先把非叶节点补全，减少情况。

       
       class 
       
       Solution {
       
       public:
       
       void 
       
       toFullTree (
       
       TreeNode 
       
       *
       
       t) {
       
       if (
       
       t 
       
       != 
       
       NULL) {
       
       if (
       
       t
       
       ->
       
       left 
       
       != 
       
       NULL 
       
       && 
       
       t
       
       ->
       
       right 
       
       == 
       
       NULL) {
       
       t
       
       ->
       
       right 
       
       = 
       
       new 
       
       TreeNode(
       
       0);
       
      }
       
       if (
       
       t
       
       ->
       
       left 
       
       == 
       
       NULL 
       
       && 
       
       t
       
       ->
       
       right 
       
       != 
       
       NULL) {
       
       t
       
       ->
       
       left 
       
       = 
       
       new 
       
       TreeNode(
       
       0);
       
      }
       
       toFullTree(
       
       t
       
       ->
       
       left);
       
       toFullTree(
       
       t
       
       ->
       
       right);
       
    }
       
  }
       
       void 
       
       postDP (
       
       TreeNode 
       
       *
       
       t) {
       
       if (
       
       t 
       
       != 
       
       NULL) {
       
       postDP(
       
       t
       
       ->
       
       left);
       
       postDP(
       
       t
       
       ->
       
       right);
       
       if (
       
       t
       
       ->
       
       left 
       
       != 
       
       NULL) {
       
       if (
       
       t
       
       ->
       
       left
       
       ->
       
       left 
       
       == 
       
       NULL 
       
       && 
       
       t
       
       ->
       
       right
       
       ->
       
       left 
       
       == 
       
       NULL) {
       
       t
       
       ->
       
       val 
       
       = 
       
       max(
       
       t
       
       ->
       
       val, 
       
       t
       
       ->
       
       left
       
       ->
       
       val 
       
       + 
       
       t
       
       ->
       
       right
       
       ->
       
       val);
       
        }
       
       if (
       
       t
       
       ->
       
       left
       
       ->
       
       left 
       
       != 
       
       NULL 
       
       && 
       
       t
       
       ->
       
       right
       
       ->
       
       left 
       
       != 
       
       NULL) {
       
       t
       
       ->
       
       val 
       
       = 
       
       max(
       
       t
       
       ->
       
       left
       
       ->
       
       val 
       
       + 
       
       t
       
       ->
       
       right
       
       ->
       
       val, 
       
       t
       
       ->
       
       val 
       
       + 
       
       t
       
       ->
       
       left
       
       ->
       
       left
       
       ->
       
       val 
       
       + 
       
       t
       
       ->
       
       left
       
       ->
       
       right
       
       ->
       
       val 
       
       + 
       
       t
       
       ->
       
       right
       
       ->
       
       left
       
       ->
       
       val 
       
       + 
       
       t
       
       ->
       
       right
       
       ->
       
       right
       
       ->
       
       val);
       
        }
       
       if (
       
       t
       
       ->
       
       left
       
       ->
       
       left 
       
       != 
       
       NULL 
       
       && 
       
       t
       
       ->
       
       right
       
       ->
       
       left 
       
       == 
       
       NULL) {
       
       t
       
       ->
       
       val 
       
       = 
       
       max(
       
       t
       
       ->
       
       left
       
       ->
       
       val 
       
       + 
       
       t
       
       ->
       
       right
       
       ->
       
       val, 
       
       t
       
       ->
       
       val 
       
       + 
       
       t
       
       ->
       
       left
       
       ->
       
       left
       
       ->
       
       val 
       
       + 
       
       t
       
       ->
       
       left
       
       ->
       
       right
       
       ->
       
       val);
       
        }
       
       if (
       
       t
       
       ->
       
       left
       
       ->
       
       left 
       
       == 
       
       NULL 
       
       && 
       
       t
       
       ->
       
       right
       
       ->
       
       left 
       
       != 
       
       NULL) {
       
       t
       
       ->
       
       val 
       
       = 
       
       max(
       
       t
       
       ->
       
       left
       
       ->
       
       val 
       
       + 
       
       t
       
       ->
       
       right
       
       ->
       
       val, 
       
       t
       
       ->
       
       val 
       
       + 
       
       t
       
       ->
       
       right
       
       ->
       
       left
       
       ->
       
       val 
       
       + 
       
       t
       
       ->
       
       right
       
       ->
       
       right
       
       ->
       
       val);
       
        }
       
      }
       
    }
       
  }
       
       int 
       
       rob(
       
       TreeNode
       
       * 
       
       root) {
       
       if (
       
       root 
       
       == 
       
       NULL) {
       
       return 
       
       0;
       
    }
       
       toFullTree(
       
       root);
       
       postDP(
       
       root);
       
       return 
       
       root
       
       ->
       
       val;
       
  }
       
};
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_14150327/5564020

当前位置：网站首页>LeetCode-337. House Robber III

LeetCode-337. House Robber III

边栏推荐

猜你喜欢

随机推荐