資訊專欄INFORMATION COLUMN
摘要：題目要求即如何從樹中選擇幾個(gè)節(jié)點(diǎn)，在確保這幾個(gè)節(jié)點(diǎn)不直接相連的情況下使其值的和最大。當(dāng)前節(jié)點(diǎn)的情況有兩種選中或是沒選中，如果選中的話，那么兩個(gè)直接子節(jié)點(diǎn)將不可以被選中，如果沒選中，那么兩個(gè)直接子節(jié)點(diǎn)的狀態(tài)可以是選中或是沒選中。
題目要求
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:
3
/
2 3
3 1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
3
/
4 5
/
1 3 1
Maximum amount of money the thief can rob = 4 + 5 = 9.
即如何從樹中選擇幾個(gè)節(jié)點(diǎn)，在確保這幾個(gè)節(jié)點(diǎn)不直接相連的情況下使其值的和最大。
思路和代碼最開始的思路我是采用自頂向下遞歸遍歷樹的形式來計(jì)算可能獲得的最大收益。當(dāng)前節(jié)點(diǎn)的情況有兩種：選中或是沒選中，如果選中的話，那么兩個(gè)直接子節(jié)點(diǎn)將不可以被選中，如果沒選中，那么兩個(gè)直接子節(jié)點(diǎn)的狀態(tài)可以是選中或是沒選中。代碼如下：
public int rob(TreeNode root) {
if(root == null) return 0;
int result1 = root.val + (root.left == null ? 0 : rob(root.left.left) + rob(root.left.right)) + (root.right == null ? 0 : rob(root.right.left) + rob(root.right.right));
int result2 = rob(root.left) + rob(root.right);
return Math.max(result1, result2);
}
這段代碼的缺陷在于，我需要遍歷這棵樹兩次，分別為了獲取選中當(dāng)前節(jié)點(diǎn)和不選中當(dāng)前節(jié)點(diǎn)的情況。而事實(shí)上我們可以在一次遍歷中就得到這兩個(gè)情況對(duì)于當(dāng)前節(jié)點(diǎn)的影響，并通過遞歸將值傳遞回上一層。很像是一種逆向思維。
public int rob2(TreeNode root) {
if (root == null) return 0;
int[] value = robSum(root);
return Math.max(value[0], value[1]);
}
private int[] robSum(TreeNode root) {
int[] res = new int[2];
if (root == null) return res;
int[] left = robSum(root.left);
int[] right = robSum(root.right);
res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
res[1] = root.val + left[0] + right[0];
return res;
}
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/71108.html
摘要：復(fù)雜度思路對(duì)于每一個(gè)位置來說，考慮兩種情況分別對(duì)和再進(jìn)行計(jì)算。用對(duì)已經(jīng)計(jì)算過的進(jìn)行保留，避免重復(fù)計(jì)算。 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, calle...
摘要：一番偵察之后，聰明的小偷意識(shí)到這個(gè)地方的所有房屋的排列類似于一棵二叉樹。如果兩個(gè)直接相連的房子在同一天晚上被打劫，房屋將自動(dòng)報(bào)警。計(jì)算在不觸動(dòng)警報(bào)的情況下，小偷一晚能夠盜取的最高金額。 Description The thief has found himself a new place for his thievery again. There is only one entranc...
摘要：解法真的非常巧妙，不過這道題里仍要注意兩個(gè)細(xì)節(jié)。中，為時(shí)，返回長(zhǎng)度為的空數(shù)組建立結(jié)果數(shù)組時(shí)，是包括根節(jié)點(diǎn)的情況，是不包含根節(jié)點(diǎn)的情況。而非按左右子樹來進(jìn)行劃分的。 Problem The thief has found himself a new place for his thievery again. There is only one entrance to this area,...
摘要：你不能連著偷兩家因?yàn)檫@樣會(huì)觸發(fā)警報(bào)系統(tǒng)?，F(xiàn)在有一個(gè)數(shù)組存放著每一家中的可偷金額，問可以偷的最大金額為多少這里考驗(yàn)了動(dòng)態(tài)編程的思想。動(dòng)態(tài)編程要求我們將問題一般化，然后再找到初始情況開始這個(gè)由一般到特殊的計(jì)算過程。 House Robber I You are a professional robber planning to rob houses along a street. Each...
摘要：注意對(duì)邊界條件的判斷，是否非空，是否長(zhǎng)度為 House Robber I Problem You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping y...
閱讀 1709·2021-10-25 09:46
閱讀 3333·2021-10-08 10:04
閱讀 2448·2021-09-06 15:00
閱讀 2886·2021-08-19 10:57
閱讀 2147·2019-08-30 11:03
閱讀 1053·2019-08-30 11:00
閱讀 2498·2019-08-26 17:10
閱讀 3632·2019-08-26 13:36
