刷题笔记5-二叉搜索树

（一）

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

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

【二叉搜索树中第K小的元素】

// 遍历二叉树的方式
public int kthSmallest(TreeNode root, int k) {
    kthSmallestTraversal(root, k);
    return res;
}

int res = 0;
int rank = 0;
private void kthSmallestTraversal(TreeNode root, int k){
    if(root == null) return;
    kthSmallestTraversal(root.left, k);
    rank++;
    if(rank == k){
        res = root.val;
    }
    kthSmallestTraversal(root.right, k);
}

【把二叉搜索树转换为累加树】

public TreeNode convertBST(TreeNode root) {
    convertBSTHelper(root);
    return root;
}
int sum = 0; // 关键!! 使用一个外部变量来记录和 大大降低了复杂度
/* 特殊的中序遍历 */
private void convertBSTHelper(TreeNode root){
    if(root == null) return;
    convertBSTHelper(root.right);
    root.val += sum;
    sum = root.val;
    convertBSTHelper(root.left);
}

（二）

1、判断BST的合法性

/* 采用后序遍历的方式 */
public boolean isValidBST(TreeNode root) {
    if(root == null) return true;

    boolean left = isValidBST(root.left);
    boolean right = isValidBST(root.right);

    if(left && right){ // 左右子树都是二叉搜索树
        return isValidBSTHelper(root);
    } else {
        return false;
    }
}

//当左右子树都是二叉搜索树时，判断加上根后是否为二叉搜索树
private boolean isValidBSTHelper(TreeNode root){
    boolean is_left_satisfied = false;
    boolean is_right_satisfied = false;

    // 左边是否满足情况
    TreeNode left_max = root.left;
    while (left_max != null && left_max.right != null){
        left_max = left_max.right;
    }
    if (left_max == null || left_max.val < root.val){
        is_left_satisfied = true;
    }

    // 右边是否满足情况
    TreeNode right_min = root.right;
    while (right_min != null && right_min.left != null){
        right_min = right_min.left;
    }
    if(right_min == null || right_min.val > root.val){
        is_right_satisfied = true;
    }

    return is_left_satisfied & is_right_satisfied;
}

/*
 * 分解问题
 * 但是由于在原函数上不好直接分解，所以需要扩展函数参数
 */
public boolean isValidBST(TreeNode root){
    return isValidBST1Helper(root, null, null);
}

private boolean isValidBSTHelper(TreeNode root, TreeNode min, TreeNode max){
    if(root == null) return true;

    if( (min != null && root.val <= min.val) ||
                (max != null && root.val >= max.val)){
        return false;
    }

    return isValidBST1Helper(root.left, min, root) &&
                   isValidBST1Helper(root.right, root, max);
}

2、在BST中搜索元素

public TreeNode searchBST(TreeNode root, int val){
    if(root == null) return null;
    if(root.val == val) {
        return root;
    }else if(root.val > val) {
        return searchBST1(root.left, val);
    } else {
        return searchBST1(root.right, val);
    }
}

3、在BST中插入元素

public TreeNode insertIntoBST(TreeNode root, int val) {
    if(root == null) return new TreeNode(val);
    if (root.val > val){
        root.left = insertIntoBST(root.left, val);
    } else {
        root.right = insertIntoBST(root.right, val);
    }
    return root;
}

4、在BST中删除元素

删除元素相对来说要复杂一些。

因为做递归的时候是将所有节点都当作根节点（一颗子树的根）来看的，所以如果需要删除，那么就要找到其左子树的最大结点或者右子树的最小结点来替换根节点。

public TreeNode deleteNode(TreeNode root, int key){
    if(root == null) return null;
    if(root.val == key){
        TreeNode left_min = root.left;
        TreeNode min_parent = null;
        while(left_min != null && left_min.right != null){
            min_parent = left_min;
            left_min = left_min.right;
        }
        if(left_min == null){ // 没有左子树
            return root.right;
        } else {
            /*
            * 这里是采用了交换两个结点的值来实现删除结点的交换
            * 也可以实际交换两个结点
            * */
            root.val = left_min.val;
            if(min_parent == null){ // 左子树的根节点就是最大，没有右节点
                root.left = left_min.left;
            } else { // 右边没有结点，左边可能有
                min_parent.right = left_min.left;
            }
            return root;
        }
    } else if(root.val > key) {
        root.left = deleteNode(root.left, key);
        return root;
    } else {
        root.right = deleteNode(root.right, key);
        return root;
    }
}

5、总结

• BST 的框架

  void BST(TreeNode root, int val){
      if(root == null) return;
      if(root.val == val){
          // 具体操作
      } else if(root.val > val){
          BST(root.left, val);
      } else {
          BST(root.right, val);
      }
  }

• 在解决递归问题时，如果发现在原函数上难以正确执行，可以考虑

  • 借助外部变量
  • 借助另外一个函数，增加函数参数

（三）

96、不同的二叉搜索树

95、不同的二叉搜索树 Ⅱ

【二叉树数量】

// 递归求解
/*
* 其实就是n个数能形成多少个合法二叉搜索树: i, i+1, i+2, ... , i+n-1
* numTrees(n) = numTrees(j-1) + numTrees(n-j) 其中 j 在 [1,n] 之间
* */
// 递归 => 很慢 递归+循环 存在重叠的部分
public int numTrees(int n) {
    if(n == 0 || n == 1) return 1;
    int sum = 0;
    for(int i = 1; i <= n; i++){ // 分别以i为根节点
        sum += numTrees(i-1) * numTrees(n-i);
    }
    return sum;
}

// 迭代 动态规划 大大降低了时间复杂度
public int numTrees1(int n) {
    int[] tmp = new int[n+1];
    tmp[0] = 1; tmp[1] = 1;
    for (int i = 2; i <= n; i++){
        for(int j = 1; j <= i; j++){
            tmp[i] += (tmp[j-1] * tmp[i-j]);
        }
    }
    return tmp[n];
}

【生成二叉树】

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

// 递归
public List<TreeNode> generateTrees(int n) {
    return generateTree(1, n);
}

private List<TreeNode> generateTree(int l, int h){
    if(l > h){
        return new ArrayList<>();
    }
    List<TreeNode> res = new ArrayList<>();

    for(int i = l; i <= h; i++){

        List<TreeNode> lefts = generateTree(l, i-1);
        List<TreeNode> rights = generateTree(i+1, h);


        for(TreeNode left : lefts){
            for (TreeNode right : rights) {
                TreeNode root = new TreeNode(i);
                root.left = left;
                root.right = right;
                res.add(root);
            }
        }
    }

    return res;
}

// 动态规划 不如递归优雅 而且 优化不了多少