python二叉搜索樹中第K小的元素是什么

發(fā)布時間：2021-12-13 16:11:57 來源：億速云閱讀：186 作者：柒染欄目：大數(shù)據(jù)

這篇文章給大家介紹python二叉搜索樹中第K小的元素是什么，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

給定一個二叉搜索樹，編寫一個函數(shù) kthSmallest 來查找其中第 k 個最小的元素。

說明：
你可以假設(shè) k 總是有效的，1 ≤ k ≤ 二叉搜索樹元素個數(shù)。

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

進(jìn)階：
如果二叉搜索樹經(jīng)常被修改（插入/刪除操作）并且你需要頻繁地查找第 k 小的值，你將如何優(yōu)化 kthSmallest 函數(shù)？

解題思路：

1,這是一個中序遍歷加剪枝優(yōu)化的題目

2，如果左子樹長度大于k，就不用遍歷右子樹了

3，在總結(jié)果中選第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 [] int    if 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，如果是左葉子，則將當(dāng)前節(jié)點加入和

2，計算當(dāng)前節(jié)點的左、右子樹的左葉子和

/** * 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)}

關(guān)于python二叉搜索樹中第K小的元素是什么就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。

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

python二叉搜索樹中第K小的元素是什么

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽