溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
今天就跟大家聊聊有關怎樣分析python二叉樹的最大路徑和，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結了以下內容，希望大家根據這篇文章可以有所收獲。
給定一個非空二叉樹，返回其最大路徑和。
本題中，路徑被定義為一條從樹中任意節點出發，達到任意節點的序列。該路徑至少包含一個節點，且不一定經過根節點。
示例 1:
輸入: [1,2,3]
1
/ \
2 3
輸出: 6
示例 2:
輸入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
輸出: 42解題思路：
對于二叉樹問題優先想到遞歸，因為劃分子問題比較容易，最大路徑和隱含問題是路徑連續
1，由于可能含根，可能不含根，所以最大和為
max(根的值，左分支含根最大和，左分支含根最大和＋根，右分支含根最大和，右分支含根最大和＋根，左分支含根最大和＋根＋右分支含根最大和，左分支不含根最大和，右分支不含根最大和)
2，上述問題包含含根（單邊）最大和子問題，求解為
max（根的值，根的值＋左含根最大和，根的值＋右含根最大和）
注意不包含：左含根最大和＋根的值＋右含根最大和，因為路線不能有分叉
代碼如下
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/func maxPathSum(root *TreeNode) int {if root==nil{return 0}if root.Left!=nil && root.Right!=nil{lr:=maxPathSumRoot(root.Left)rr:=maxPathSumRoot(root.Right)l:=maxPathSum(root.Left)r:=maxPathSum(root.Right)a:=[]int{root.Val,root.Val+lr,root.Val+rr,lr,rr,root.Val+lr+rr,l,r}return max(a)}else if root.Left!=nil {lr:=maxPathSumRoot(root.Left)l:=maxPathSum(root.Left)a:=[]int{root.Val,root.Val+lr,lr,l}return max(a)}else if root.Right!=nil{rr:=maxPathSumRoot(root.Right)r:=maxPathSum(root.Right)a:=[]int{root.Val,root.Val+rr,rr,r}return max(a)}return root.Val}func max(arr []int) int{max:=-1<<31for i:=0;i<len(arr);i++{if max<arr[i]{max=arr[i]}}return max}func maxPathSumRoot(root *TreeNode) int {if root==nil{return 0}l:=maxPathSumRoot(root.Left)r:=maxPathSumRoot(root.Right)return max([]int{l+root.Val,r+root.Val,root.Val})}
看完上述內容，你們對怎樣分析python二叉樹的最大路徑和有進一步的了解嗎？如果還想了解更多知識或者相關內容，請關注億速云行業資訊頻道，感謝大家的支持。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
