LeetCode：337. House Robber III（偷窃问题）

柔情只为你懂 2022-04-04 12:54 165阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

**问目录：**

题目描述：

java实现方法1：（递归算法）

python实现方式1：

java实现方法2:（另一种递归思路）

python实现方式2：

源码github地址：https://github.com/zhangyu345293721/leetcode

--------------------

### 题目描述： ###

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]
    
         3
        / \
       2   3
        \   \ 
         3   1
    
    输出: 7 
    解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

输入: [3,4,5,1,3,null,1]
    
         3
        / \
       4   5
      / \   \ 
     1   3   1
    
    输出: 9
    解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

来源：力扣（LeetCode）

--------------------

### java实现方法1：（递归算法） ###

/**
         * 找出抢劫最大结果
         *
         * @param root 根节点
         * @return 最大值
         */
        public int rob(TreeNode root) {
            int[] result = helper(root);
            return Math.max(result[0], result[1]);
        }
    
        /**
         * 帮助方法
         *
         * @param node 节点
         * @return 数组
         */
        public int[] helper(TreeNode node) {
            if (node == null) {
                return new int[]{0, 0};
            }
            if (node.left == null && node.right == null) {
                return new int[]{node.val, 0};
            }
            int[] l = helper(node.left);
            int[] r = helper(node.right);
            return new int[]{node.val + l[1] + r[1], Math.max(l[0], l[1]) + Math.max(r[0], r[1])};
        }

时间复杂度：O(n)

空间复杂度：O(n)

--------------------

### python实现方式1： ###

def helper(node: TreeNode) -> List[int]:
        '''
            帮助方法
        Args:
            node: 节点
        Returns:
            数组
        '''
        if node == None:
            return [0, 0]
        if not node.left and not node.right:
            return [node.val, 0]
        l = helper(node.left)
        r = helper(node.right)
        return [node.val + l[1] + r[1], max(r[0], r[1]) + max(l[0] + l[1])]
    
    
    def rob(root: TreeNode) -> int:
        '''
            找出抢劫最大值
        Args:
            root: 跟节点
        Returns:
            最大值
        '''
        result = helper(root)
        return max(result[0], result[1])

时间复杂度：O(n)

空间复杂度：O(n)

--------------------

### java实现方法2:（另一种递归思路） ###

/**
         * 找出抢劫最大结果
         *
         * @param root 根节点
         * @return 最大值
         */
        public int rob2(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int val = 0;
            if (root.left != null) {
                val += rob2(root.left.left) + rob2(root.left.right);
            }
            if (root.right != null) {
                val += rob2(root.right.left) + rob2(root.right.right);
            }
            return Math.max(val + root.val, rob2(root.left) + rob2(root.right));
        }

时间复杂度:O(n)

空间复杂度:O(n)

--------------------

### python实现方式2： ###

def rob2(root: TreeNode) -> int:
        '''
            找出抢劫最大值
        Args:
            root: 跟节点
        Returns:
            最大值
        '''
        if not root:
            return 0
        val = 0
        if root.left :
            val += rob2(root.left.left) + rob2(root.left.right)
        if root.right :
            val += rob2(root.right.left) + rob2(root.right.right)
        return max(val + root.val, rob2(root.right) + rob2(root.left))

时间复杂度:O(n)

空间复杂度:O(n)

--------------------

### 源码github地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode