How does C++ calculate the K smallest element in the binary search tree

This article mainly explains "how C++ calculates the K smallest element in the binary search tree". The content in the article is simple and clear, and it is easy to learn and understand. let's study and learn how C++ calculates the K smallest element in the binary search tree.

Algorithm:

The core idea of this kind of problem is to use the middle order traversal of the binary tree from small to large, transform it into an array, and then operate on the ordered array.

Special note: there may be duplicate nodes in the converted array, so we need to deduplicate the array.

Topic 1: the second smallest node in the binary tree

Code implementation:

/ * Definition for a binary tree node. * type TreeNode struct {* Val int * Left * TreeNode * Right * TreeNode * * / func findSecondMinimumValue (root * TreeNode) int {res: = midOrder (root) m: = make (mapping [int] for _, v:=range res {m [v] = v} resp: = [] int {} for _, v:=range m {resp = append (resp) V)} if len (resp) > = 2 {sort.Ints (resp) return resp [1]} return-1} func midOrder (root * TreeNode) (res [] int) {if root = = nil {return} res = append (res,midOrder (root.Left).) Res = append (res,root.Val) res = append (res,midOrder (root.Right)...) Return}

Topic 2: the K smallest element in the binary search tree

Code implementation:

/ * Definition for a binary tree node. * type TreeNode struct {* Val int * Left * TreeNode * Right * TreeNode *} * / func kthSmallest (root * TreeNode K int) int {if root = = nil {return 0} res: = midOrder (root) if k > len (res) {return 0} return res [k-1]} func midOrder (root * TreeNode) [] int {if root = = nil {return nil} res: = [] int {} res = append (res,midOrder (root.Left)...) Res = append (res,root.Val) res = append (res,midOrder (root.Right)...) Return res} Thank you for your reading, the above is the content of "how C++ calculates the K smallest element in the binary search tree". After the study of this article, I believe you have a deeper understanding of how C++ calculates the K smallest element in the binary search tree, and the specific use still needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!