這篇文章給大家介紹怎樣求python二叉樹(shù)路徑和，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對(duì)大家能有所幫助。

成都創(chuàng)新互聯(lián)主要從事成都做網(wǎng)站、網(wǎng)站建設(shè)、外貿(mào)營(yíng)銷網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)呼倫貝爾,10多年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來(lái)電咨詢建站服務(wù):18982081108

給定一個(gè)二叉樹(shù)和一個(gè)目標(biāo)和，判斷該樹(shù)中是否存在根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑，這條路徑上所有節(jié)點(diǎn)值相加等于目標(biāo)和。

說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。

示例: 
給定如下二叉樹(shù)，以及目標(biāo)和 sum = 22，

5
            / \
           4   8
          /   / \
         11  13  4
        /  \      \
       7    2      1

返回 true, 因?yàn)榇嬖谀繕?biāo)和為 22 的根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑 5->4->11->2。

解題思路：

1，對(duì)于二叉樹(shù)類型題目一般都是遞歸解

2，遞歸有兩種：自根向下和自葉子向上

3，對(duì)于相等類型題目和最大值題目解題思路相反，本題采用自根向下

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */func hasPathSum(root *TreeNode, sum int) bool {    if root==nil{        return false    }    if root.Left==nil && root.Right==nil{        return root.Val==sum    }    return hasPathSum(root.Left,sum-root.Val)||hasPathSum(root.Right,sum-root.Val)}

給定一個(gè)二叉樹(shù)和一個(gè)目標(biāo)和，找到所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)路徑總和等于給定目標(biāo)和的路徑。

說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。

示例:
給定如下二叉樹(shù)，以及目標(biāo)和 sum = 22，

5
            / \
           4   8
          /   / \
         11  13  4
        /  \    / \
       7    2  5   1

返回:

[
  [5,4,11,2],
  [5,8,4,5]
]

思路：

1，同樣是遞歸，需要每一次把走過(guò)的路徑存下來(lái)傳下去，如果滿足條件就返回，否則舍棄

2，注意golang 傳slice 和map的坑，雖然slice的len是每次傳值，但是數(shù)據(jù)地址是一樣的，所以會(huì)覆蓋掉，每次數(shù)據(jù)結(jié)果都不一樣

3，解決辦法copy函數(shù)進(jìn)行復(fù)制。

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */func pathSum(root *TreeNode, sum int) [][]int {    var r [][]int    if root ==nil{        return r    }    var temp []int    return walk(root,sum,temp)}
func walk(root *TreeNode, sum int,temp1 []int)([][]int){     var r [][]int    if root==nil{        return r    }    temp:=make([]int,len(temp1))    copy(temp,temp1)     temp=append(temp,root.Val)   //fmt.Println(root,temp,sum)     if root.Left==nil && root.Right==nil{        if root.Val==sum{            r=append(r,temp)        // fmt.Println(root,temp,sum,r)            return r        }         return r     }                    tl:=walk(root.Left,sum-root.Val,temp)        tr:=walk(root.Right,sum-root.Val,temp)
         if len(tl)>0 {             r=append(r,tl...)         }         if len(tr)>0 {             r=append(r,tr...)         }    return r}

關(guān)于怎樣求python二叉樹(shù)路徑和就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到。

本文標(biāo)題：怎樣求python二叉樹(shù)路徑和
轉(zhuǎn)載來(lái)于：http://www.rwnh.cn/article2/gjhhic.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站內(nèi)鏈、做網(wǎng)站、網(wǎng)頁(yè)設(shè)計(jì)公司、微信公眾號(hào)、虛擬主機(jī)、網(wǎng)站收錄

廣告

聲明：本網(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)