Leetcode-337 打家劫舍3

admin2024-06-21  11

力扣題目:

小偷又發(fā)現了一個(gè)新的可行竊的地區。這個(gè)地區只有一個(gè)入口,我們稱(chēng)之為?root?。

除了?root?之外,每棟房子有且只有一個(gè)“父“房子與之相連。一番偵察之后,聰明的小偷意識到“這個(gè)地方的所有房屋的排列類(lèi)似于一棵二叉樹(shù)”。 如果?兩個(gè)直接相連的房子在同一天晚上被打劫?,房屋將自動(dòng)報警。

給定二叉樹(shù)的?root?。返回?在不觸動(dòng)警報的情況下?,小偷能夠盜取的最高金額?。

示例 1:

Leetcode-337 打家劫舍3,第1張

輸入: root = [3,2,3,null,3,null,1]
輸出: 7 
解釋:?小偷一晚能夠盜取的最高金額 3 + 3 + 1 = 7

示例 2:

Leetcode-337 打家劫舍3,第2張

輸入: root = [3,4,5,1,3,null,1]
輸出: 9
解釋:?小偷一晚能夠盜取的最高金額 4 + 5 = 9

提示:

  • 樹(shù)的節點(diǎn)數在?[1, 104]?范圍內
  • 0 <= Node.val <= 104

解題思路:

在一個(gè)給定的二叉樹(shù)中,找到從根節點(diǎn)到葉子節點(diǎn)的路徑上,能夠偷取的最大金額的問(wèn)題。

使用深度優(yōu)先搜索算法(DFS)進(jìn)行遞歸求解,通過(guò)動(dòng)態(tài)規劃的方式計算每個(gè)節點(diǎn)的最大金額。在每個(gè)節點(diǎn)處,可以選擇偷取該節點(diǎn)的金額或者不偷取,但不能同時(shí)偷取父節點(diǎn)和子節點(diǎn)的金額。返回從根節點(diǎn)到葉子節點(diǎn)的路徑上能夠偷取的最大金額。
函數rob調用dfs函數來(lái)計算每個(gè)節點(diǎn)的最大金額,并返回根節點(diǎn)處的最大金額。dfs函數返回一個(gè)Pair對象,其中g(shù)etKey()表示不偷取當前節點(diǎn)的金額,getValue()表示偷取當前節點(diǎn)的金額。在遞歸過(guò)程中,對于每個(gè)節點(diǎn),先遞歸計算其左子樹(shù)和右子樹(shù)的最大金額,然后根據當前節點(diǎn)是否被偷取,計算出當前節點(diǎn)的最大金額。最后,將當前節點(diǎn)的最大金額作為結果返回。

java代碼:


  package org.example;

import javafx.util.Pair;

import javax.swing.tree.TreeNode;

public class Leetcode337 {
    public static int rob(TreeNode root) {
        Pair<Integer, Integer> dp = dfs(root);
        return Math.max(dp.getKey(), dp.getValue());
    }
    private static Pair<Integer, Integer> dfs(TreeNode root) {
        if(root == null) {
            return new Pair<>(0, 0);
        }
        Pair<Integer, Integer> dpLeft = dfs(root.left);
        Pair<Integer, Integer> dpRight = dfs(root.right);
        int val1 = Math.max(dpLeft.getKey(), dpLeft.getValue()) +
                Math.max(dpRight.getValue(), dpRight.getKey());//不偷
        int val2 = dpLeft.getKey() + dpRight.getKey() + root.val;
        return new Pair<>(val1, val2);
    }


    public static void main(String[] args) {
        // 測試代碼示例
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(3);
        root.right.right = new TreeNode(1);

        int result = rob(root);
        System.out.println(result); // 輸出計算結果
    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}
本文來(lái)自互聯(lián)網(wǎng)用戶(hù)投稿,該文觀(guān)點(diǎn)僅代表作者本人,不代表本站立場(chǎng)。本站僅提供信息存儲空間服務(wù),不擁有所有權,不承擔相關(guān)法律責任。如若轉載,請注明原文出處。如若內容造成侵權/違法違規/事實(shí)不符,請聯(lián)系SD編程學(xué)習網(wǎng):675289112@qq.com進(jìn)行投訴反饋,一經(jīng)查實(shí),立即刪除!
一级毛片在线一区二区-亚洲精品无码专区土豆网在线播放-亚洲无乱码一区二区三区-亚洲一区二区三区精品