溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

如何用打家劫舍的思維分析python二叉樹

發(fā)布時(shí)間：2021-12-13 16:06:33 來(lái)源：億速云 閱讀：204 作者：柒染 欄目：大數(shù)據(jù)

如何用打家劫舍的思維分析python二叉樹，相信很多沒(méi)有經(jīng)驗(yàn)的人對(duì)此束手無(wú)策，為此本文總結(jié)了問(wèn)題出現(xiàn)的原因和解決方法，通過(guò)這篇文章希望你能解決這個(gè)問(wèn)題。

在上次打劫完一條街道之后和一圈房屋后，小偷又發(fā)現(xiàn)了一個(gè)新的可行竊的地區(qū)。這個(gè)地區(qū)只有一個(gè)入口，我們稱之為“根”。 除了“根”之外，每棟房子有且只有一個(gè)“父“房子與之相連。一番偵察之后，聰明的小偷意識(shí)到“這個(gè)地方的所有房屋的排列類似于一棵二叉樹”。 如果兩個(gè)直接相連的房子在同一天晚上被打劫，房屋將自動(dòng)報(bào)警。

計(jì)算在不觸動(dòng)警報(bào)的情況下，小偷一晚能夠盜取的最高金額。

示例 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.

解題思路：

1，有兩種選擇

A，打劫根節(jié)點(diǎn)和孫子節(jié)點(diǎn)

B，打劫孩子節(jié)點(diǎn)

2，有5種邊界情況

A，根節(jié)點(diǎn)空

B，左右孩子非空

C，左右孩子均空

D，左孩子空

E，右孩子空

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */func rob(root *TreeNode) int {    val:=0    if root==nil{        return val    }        if root.Left!=nil && root.Right!=nil{        ll:=rob(root.Left.Left)        lr:=rob(root.Left.Right)                rl:=rob(root.Right.Left)        rr:=rob(root.Right.Right)                l:=rob(root.Left)        r:=rob(root.Right)                if root.Val+ll+lr+rr+rl>l+r{            return root.Val+ll+lr+rr+rl        }        return l+r    }        if root.Left!=nil{        ll:=rob(root.Left.Left)        lr:=rob(root.Left.Right)                l:=rob(root.Left)                if root.Val+ll+lr>l{            return root.Val+ll+lr        }        return l            }        if root.Right!=nil{        rl:=rob(root.Right.Left)        rr:=rob(root.Right.Right)                r:=rob(root.Right)                if root.Val+rl+rr>r{            return root.Val+rl+rr        }        return r    }    return root.Val}

看完上述內(nèi)容，你們掌握如何用打家劫舍的思維分析python二叉樹的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！

向AI問(wèn)一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手