溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章給大家介紹python二叉搜索樹中第K小的元素是什么，內容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。
給定一個二叉搜索樹，編寫一個函數 kthSmallest 來查找其中第 k 個最小的元素。
說明：
你可以假設 k 總是有效的，1 ≤ k ≤ 二叉搜索樹元素個數。
示例 1:
輸入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
輸出: 1示例 2:
輸入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
輸出: 3進階：
如果二叉搜索樹經常被修改（插入/刪除操作）并且你需要頻繁地查找第 k 小的值，你將如何優化 kthSmallest 函數？
解題思路：
1,這是一個中序遍歷加剪枝優化的題目
2，如果左子樹長度大于k，就不用遍歷右子樹了
3，在總結果中選第k個
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/func kthSmallest(root *TreeNode, k int) int {r:=mid(root,k)return r[k-1]}func mid(root*TreeNode,k int)[]int{var r [] intif root==nil{return r}l:=mid(root.Left,k)if len(l)>=k{return l}r=append(l,root.Val)if len(l)+1>=k{return r}rr:=mid(root.Right,k-len(l)-1)r=append(r,rr...)return r}
計算給定二叉樹的所有左葉子之和。
示例：
3
/ \
9 20
/ \
15 7
在這個二叉樹中，有兩個左葉子，分別是 9 和 15，所以返回 24解題思路：
1，如果是左葉子，則將當前節點加入和
2，計算當前節點的左、右子樹的左葉子和
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */func sumOfLeftLeaves(root *TreeNode) int { if root==nil{ return 0 } if root.Left!=nil{ if root.Left.Left==nil&&root.Left.Right==nil{ return root.Left.Val + sumOfLeftLeaves(root.Right) } } return sumOfLeftLeaves(root.Left)+ sumOfLeftLeaves(root.Right)}
關于python二叉搜索樹中第K小的元素是什么就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
