タイトル:ツリーのK番目の小さなノードを見つけるために、二叉検索ツリー(BST)を指定します。

*考察点

基礎データ構造の理解と符号化能力

再帰使用

*例

       5
      / \
     3   6
    / \
   2   4
  /
 1
 

説明:入力Kが1<=K<=(ノード数)を満たすことを保証する
木に関する問題は,一目で再帰的に解き,左右の子木がそれぞれ遍歴することを考える.二叉探索ツリーの性質を連想し、rootが左サブツリーより大きく、右サブツリーより小さく、左サブツリーのノード数がK-1に等しい場合、rootは結果であり、そうでない場合、左サブツリーのノード数が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 {
    private class ResultType {
    
        boolean found;  //  
        
        int val;  //  
        ResultType(boolean found, int val) {
            this.found = found;
            this.val = val;
        }
    }

    public int kthSmallest(TreeNode root, int k) {
        return kthSmallestHelper(root, k).val;
    }

    private ResultType kthSmallestHelper(TreeNode root, int k) {
        if (root == null) {
            return new ResultType(false, 0);
        }

        ResultType left = kthSmallestHelper(root.left, k);

        //  ， 
        if (left.found) {
            return new ResultType(true, left.val);
        }

        //   = K-1，  root  
        if (k - left.val == 1) {
            return new ResultType(true, root.val);
        }

        //  
        ResultType right = kthSmallestHelper(root.right, k - left.val - 1);
        if (right.found) {
            return new ResultType(true, right.val);
        }

        //  ， 
        return new ResultType(false, left.val + 1 + right.val);
    }
}

二叉探索ツリーを指定し、関数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関数を最適化するにはどうすればいいですか?中間パスの使用

class Solution {
    List list = new ArrayList();
    public void dfs(TreeNode root){
        if(root == null)
            return ;
        dfs(root.left);
        list.add(root.val);
        dfs(root.right);
    }
    public int kthSmallest(TreeNode root, int k) {
        dfs(root);
        for(int i=0;i

再帰(ノード数の計算)を使用します。

class Solution {    
    public int count(TreeNode root){
        if(root == null)
            return 0;
        return 1 + count(root.left) + count(root.right);
    }
    public int kthSmallest(TreeNode root, int k) {
        int num = count(root.left);
        if(num == k-1)
            return root.val;
        if(num > k-1)
            return kthSmallest(root.left,k);
        return kthSmallest(root.right,k - num-1);
    }
}

参照リンク:

https://blog.csdn.net/xuchonghao/article/details/80770490
https://github.com/debitCrossBlockchain/interview__reference/blob/master/01.%E9%98%BF%E9%87%8C%E7%AF%87/1.1.3%20%E7%BB%99%E5%AE%9A%E4%B8%80%E4%B8%AA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91(BST)%EF%BC%8C%E6%89%BE%E5%88%B0%E6%A0%91%E4%B8%AD%E7%AC%AC%20K%20%E5%B0%8F%E7%9A%84%E8%8A%82%E7%82%B9.md