LeetCode中級二叉探索ツリーのk番目の小さい要素
二叉探索ツリーが与えられ、関数
説明:kは常に有効であり、1≦k≦二叉探索ツリー要素の個数であると仮定できます.
例1:
例2:
ステップアップ:二叉検索ツリーが頻繁に変更(挿入/削除操作)され、k番目の小さな値を頻繁に検索する必要がある場合、
私の解題の構想:1.再帰を使用して、検索ツリーのすべての要素を昇順にキューに格納します.
2.k-1の数をポップアップして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-1の数をポップアップしてk番目に戻せばいいです
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int kthSmallest(TreeNode root,int k){
Queue kthResult=new LinkedList<>();
result(kthResult,root);
for (int i = 0; i < k-1; i++) {
kthResult.poll();
}
return kthResult.poll();
}
public void result(Queue queue, TreeNode root){
if(root==null){
return ;
}
result(queue,root.left);
queue.add(root.val);
result(queue,root.right);
return ;
}
}