337. House Robber III

栏目: 数据库 · 发布时间: 4年前

内容简介: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 plac

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.

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.

难度:medium

题目:

小偷又发现了一个新的地方来实施的偷盗计划。 这个地方只有一个入口叫“根”。除了这个根之外,每个房间有且仅有一个父房间。一番游览过后,聪明的小偷意识到这里所有的房子形成了一棵二叉树。如果在同一晚上有任何两个相邻的房子遭遇偷盗就会触发警报。

在这个晚上小偷如何决策在不触发警报的情况下获取最大的盗资。

思路:

二叉树遍历

Runtime: 733 ms, faster than 27.11% of Java online submissions for House Robber III.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // rob root,     g(root)     = root.val + f(root.left.left) + f(root.left.right) + f(root.right.left) + f(root.right.right)
    // not rob root, g(not_root) = f(root.left) + f(root.right);
    // f(root) = Math.max(g(root), g(not_root))
    
    public int rob(TreeNode root) {
        if (null == root) {
            return 0;
        }

        TreeNode left = root.left;
        int leftSum = (null == left) ? 0 : (rob(left.left) + rob(left.right));
        
        TreeNode right = root.right;
        int rightSum = (null == right) ? 0 : (rob(right.left) + rob(right.right));
        
        return Math.max(root.val + leftSum + rightSum, rob(left) + rob(right));
    }
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

High Performance Python

High Performance Python

Micha Gorelick、Ian Ozsvald / O'Reilly Media / 2014-9-10 / USD 39.99

If you're an experienced Python programmer, High Performance Python will guide you through the various routes of code optimization. You'll learn how to use smarter algorithms and leverage peripheral t......一起来看看 《High Performance Python》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

URL 编码/解码
URL 编码/解码

URL 编码/解码

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具