BST(二叉搜索树)练习_bst二叉树单元测试答案

学习东哥算法小抄笔记：文章链接

内容

二叉搜索树
中序遍历对BST的意义
      二叉搜索树中第K小的元素
      把二叉搜索树转换为累加树
BST基本操作
      验证二叉搜索树
      二叉搜索树中的搜索
      二叉搜索树中的插入操作
      删除二叉树搜索树中的节点
计算所有合法 BST
      不同的二叉搜索树
      不同的二叉搜索树II
二叉树后序遍历应用
      二叉搜索子树的最大键值和

二叉搜索树

定义

1、对于 BST 的每一个节点 node，左子树节点的值都比 node 的值要小，右子树节点的值都比 node 的值大。
2、对于 BST 的每一个节点 node，它的左侧子树和右侧子树都是 BST。

性质

BST 的中序遍历结果是有序的（升序）。

void traverse(TreeNode root) {
    if (root == null) return;
    traverse(root.left);
    // 中序遍历代码位置
    print(root.val);
    traverse(root.right);
}
1
2
3
4
5
6
7

中序遍历对BST的意义 例题

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

代码：

// C++代码
class Solution {
public:
    int res;
    int kthSmallest(TreeNode* root, int k) {
        DFS(root,k);
        return res;
    }
    void DFS(TreeNode* node,int &k){
        if(node==nullptr){
            return ;
        }
        DFS(node->left,k);
        --k;
        if(k==0){
            res = node->val;
            return ;
        }
        DFS(node->right,k);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

题目描述：
解释说明：

对于结点6来说，21 = 6 + 7 + 8（即包含自己的右半部分结点值的和）

思想：

改变递归顺序，使其降序遍历，先右后左就能累加右边节点的值。

class Solution {
public:
    int sum = 0;
    TreeNode* convertBST(TreeNode* root) {
        DFS(root);
        return root;
    }
    void DFS(TreeNode *node){
        if(node==nullptr){
            return ;
        }
        DFS(node->right);
        sum += node->val;
        node->val = sum;
        DFS(node->left);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

BST基本操作 例题

1. 力扣98 验证二叉搜索树

boolean isValidBST(TreeNode root) {
    return isValidBST(root, null, null);
}
/* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val */
boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
    // base case
    if (root == null) return true;
    // 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
    if (min != null && root.val <= min.val) return false;
    if (max != null && root.val >= max.val) return false;
    // 限定左子树的最大值是 root.val，右子树的最小值是 root.val
    return isValidBST(root.left, min, root) 
        && isValidBST(root.right, root, max);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2. 力扣700 二叉搜索树中的搜索

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(root==nullptr){
            return nullptr;
        }
        if(root->val>val){
            return searchBST(root->left,val);
        }
        if(root->val<val){
            return searchBST(root->right,val);
        }
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3. 力扣701 二叉搜索树中的插入操作

**个人疑惑：**插入节点均可以在最后一层进行

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root==nullptr){
            return new TreeNode(val);
        }
        if(val<root->val){
            root->left = insertIntoBST(root->left,val);
        }
        if(val>root->val){
            root->right = insertIntoBST(root->right,val);
        }
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4. 力扣450 删除二叉树搜索树中的节点

解答： 要删除一个节点可以用左子树的最后一个节点或者右子树的第一个节点做替代。（最后一个和第一个是相对于中序遍历的顺序）。

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root==nullptr){
            return nullptr;
        }
        if(root->val==key){
            // 恰好是末端节点，两个子节点都为空，那么它可以当场去世
            // 只有一个非空子节点，那么它要让这个孩子接替自己的位置
            // 以下两个if可以实现此操作
            if(root->left==nullptr){
                return root->right;
            }
            if(root->right==nullptr){
                return root->left;
            }
            TreeNode* node = getMin(root->right); 
            root->val = node->val;
            root->right = deleteNode(root->right,root->val);
        }else if(root->val>key){
            root->left = deleteNode(root->left,key);
        }else if(root->val<key){
            root->right = deleteNode(root->right,key);
        }
        return root;
    }
    TreeNode* getMin(TreeNode* temp){
        while(temp->left!=nullptr){
            temp = temp->left;
        }
        return temp;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

总结：BST代码框架

void BST(TreeNode root, int target) {
    if (root.val == target)
        // 找到目标，做点什么
    if (root.val < target) 
        BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}
1
2
3
4
5
6
7
8

计算所有合法 BST 例题

1. 力扣96 不同的二叉搜索树

思想一： 这道题可以用动态规划的思想解决，因为针对一个节点，其一边不管是1和2还是3和4，能构造的子树数量是一样的，都是两个。由此可见，和具体数字大小无关。

class Solution {
public:
    int numTrees(int n) {
        if(n==0 || n==1){
            return 1;
        }else if(n==2){
            return 2;
        }
        int* p = new int[n+1];
        memset(p,0,sizeof(int)*(n+1));
        p[0] = p[1] = 1;
        p[2] = 2;
        for(int i=3;i<=n;i++){
            for(int j=0;j<i;j++){
                p[i] += p[j]*p[i-1-j];
            }
        }
        return p[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

思想二： 递归解决，并消除重叠子问题

int[][] memo;

int numTrees(int n) {
    // 备忘录的值初始化为 0
    memo = new int[n + 1][n + 1];
    return count(1, n);
}

int count(int lo, int hi) {
    if (lo > hi) return 1;
    // 查备忘录
    if (memo[lo][hi] != 0) {
        return memo[lo][hi];
    }

    int res = 0;
    for (int mid = lo; mid <= hi; mid++) {
        int left = count(lo, mid - 1);
        int right = count(mid + 1, hi);
        res += left * right;
    }
    // 将结果存入备忘录
    memo[lo][hi] = res;

    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

2. 力扣95 不同的二叉搜索树II

思想： 这道题应该是上一道题的进阶了，用上一题的思想一是不能解决的。

/* 主函数 */
public List<TreeNode> generateTrees(int n) {
    if (n == 0) return new LinkedList<>();
    // 构造闭区间 [1, n] 组成的 BST 
    return build(1, n);
}

/* 构造闭区间 [lo, hi] 组成的 BST */
List<TreeNode> build(int lo, int hi) {
    List<TreeNode> res = new LinkedList<>();
    // base case
    if (lo > hi) {
        res.add(null);
        return res;
    }

    // 1、穷举 root 节点的所有可能。
    for (int i = lo; i <= hi; i++) {
        // 2、递归构造出左右子树的所有合法 BST。
        List<TreeNode> leftTree = build(lo, i - 1);
        List<TreeNode> rightTree = build(i + 1, hi);
        // 3、给 root 节点穷举所有左右子树的组合。
        for (TreeNode left : leftTree) {
            for (TreeNode right : rightTree) {
                // i 作为根节点 root 的值
                TreeNode root = new TreeNode(i);
                root.left = left;
                root.right = right;
                res.add(root);
            }
        }
    }

    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

二叉树后续遍历应用

二叉树练习中有谈到二叉树相关题目最核心的思路是明确当前节点需要做的事情是什么。

后序遍历的代码框架：

void traverse(TreeNode root) {
    traverse(root.left);
    traverse(root.right);
    /* 后序遍历代码的位置 */
    /* 在这里处理当前节点 */
}
1
2
3
4
5
6

力扣 1373. 二叉搜索子树的最大键值和

注：如果当前节点要做的事情需要通过左右子树的计算结果推导出来，就要用到后序遍历。（ 东哥答题 ）

// C++通过代码
class Solution {
public:
    int maxSum = 0;
    int maxSumBST(TreeNode* root) {
        traverse(root);
        return maxSum;
    }
    int* traverse(TreeNode* root){
      // res[0]:是否是BST,res[1]:最小值，res[2]:最大值，res[3]:和
      int* res = new int[4];
      if(root==nullptr){
          res[0] = 1;
          res[1] = INT_MAX;
          res[2] = INT_MIN;
          res[3] = 0;
          return res;
      }
      int* a = traverse(root->left);
      int* b = traverse(root->right);
      if(a[0]==1 && b[0]==1 && root->val>a[2] && root->val<b[1]){
          int sum = a[3] + b[3] + root->val;
          maxSum = max(sum,maxSum);
          res[0] = 1;
          res[1] = min(a[1],root->val);;
          res[2] = max(b[2],root->val);
          res[3] = sum;
          return res;
      }
      res[0] = 0;
      return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33