Shulou(Shulou.com)06/01 Report--

This article introduces what is the smallest element in the python binary search tree, the content is very detailed, interested friends can refer to, I hope it can be helpful to you.

Given a binary search tree, write a function kthSmallest to find the k smallest element in it.

Description:

You can assume that k is always valid, 1 ≤ k ≤ the number of binary search tree elements.

Example 1:

Input: root = [3, 1, 4, 4, 2], k = 1

three

/\

1 4

\

two

Output: 1

Example 2:

Input: root = [5, 5, 3, 6, 6, 2, 4, and 4], k = 3

five

/\

3 6

/\

2 4

/

one

Output: 3

Advanced:

If the binary search tree is often modified (insert / delete operations) and you need to find k values frequently, how do you optimize the kthSmallest function?

Ideas for solving the problem:

1, this is a mid-order traversal plus pruning optimization problem

2, if the length of the left subtree is greater than k, you don't have to traverse the right subtree.

3, select the k out of the total result

/ * 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 (lmemroot.Val) if len (l) + 1 > = k {return r} rr:=mid (root.Right,k-len (l)-1) r=append (rMagner...) Return r}

Calculates the sum of all the left leaves of a given binary tree.

Example:

three

/\

9 20

/\

15 7

In this binary tree, there are two left leaves, 9 and 15, respectively, so return 24

Ideas for solving the problem:

1, if it is a left leaf, add the current node and

2, calculate the left leaves and the left leaves of the left and right subtrees of the current node

/ * 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.LeftExpendnil {if root.Left.Left==nil&&root.Left.Right==nil {return root.Left.Val + sumOfLeftLeaves (root.Right)} return sumOfLeftLeaves (root.Left) + sumOfLeftLeaves ( Root.Right)} so much about what is the smallest element in the python binary search tree. I hope the above content can be of some help to you and learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.