刷题笔记22——二叉搜索树BST

从叶到花,或从花到叶,于科研是一个过程,而于生命自身则永远只在此刻。花和叶都是一种记忆方式,果子同时也是种子。生命是闪耀的此刻,不是过程,就像芳香不需要道路一样。 ——顾城《一个人应该活得是他自己并且干净》

• 二叉搜索树：右子树节点值都比node大，左子树节点值都比node小

1038. 从二叉搜索树到更大和树

class Solution {
    int sum = 0;
    public TreeNode bstToGst(TreeNode root) {
        if(root != null){
            bstToGst(root.right);
            sum = sum + root.val;
            root.val = sum;
            bstToGst(root.left);
        }
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

538. 把二叉搜索树转换为累加树

class Solution {
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        sumBST(root);
        return root;
    }

    public void sumBST(TreeNode root){
        if(root==null) return;
        sumBST(root.right);
        sum = sum + root.val;
        root.val = sum;
        sumBST(root.left);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

AVL 树，红黑树, B+ 树，线段树

230. 二叉搜索树中第K小的元素

class Solution {
    int m = 0;
    int result = -1;
    public int kthSmallest(TreeNode root, int k) {
        findkth(root,k);
        return result;
    }

    public void findkth(TreeNode root,int k){
        if(root==null) return;
        kthSmallest(root.left,k);
        m++;
        if(m==k){
            result = root.val;
        }
        kthSmallest(root.right,k);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18