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

創(chuàng)新互聯(lián)自成立以來(lái)，一直致力于為企業(yè)提供從網(wǎng)站策劃、網(wǎng)站設(shè)計(jì)、做網(wǎng)站、網(wǎng)站制作、電子商務(wù)、網(wǎng)站推廣、網(wǎng)站優(yōu)化到為企業(yè)提供個(gè)性化軟件開(kāi)發(fā)等基于互聯(lián)網(wǎng)的全面整合營(yíng)銷服務(wù)。公司擁有豐富的網(wǎng)站建設(shè)和互聯(lián)網(wǎng)應(yīng)用系統(tǒng)開(kāi)發(fā)管理經(jīng)驗(yàn)、成熟的應(yīng)用系統(tǒng)解決方案、優(yōu)秀的網(wǎng)站開(kāi)發(fā)工程師團(tuán)隊(duì)及專業(yè)的網(wǎng)站設(shè)計(jì)師團(tuán)隊(duì)。

在上次打劫完一條街道之后和一圈房屋后，小偷又發(fā)現(xiàn)了一個(gè)新的可行竊的地區(qū)。這個(gè)地區(qū)只有一個(gè)入口，我們稱之為“根”。 除了“根”之外，每棟房子有且只有一個(gè)“父“房子與之相連。一番偵察之后，聰明的小偷意識(shí)到“這個(gè)地方的所有房屋的排列類似于一棵二叉樹(shù)”。 如果兩個(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二叉樹(shù)的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！

網(wǎng)站標(biāo)題：如何用打家劫舍的思維分析python二叉樹(shù)
本文鏈接：http://www.aaarwkj.com/article34/pdcgpe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)建站、建站公司、電子商務(wù)、營(yíng)銷型網(wǎng)站建設(shè)、網(wǎng)站制作、網(wǎng)站導(dǎo)航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)