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 1Output: 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 1Output: 9Explanation: 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)); }}