二叉搜索树-EmiyaCC 摘录室

二叉搜索树转链表
- 二叉搜索树中第K小的元素

二叉搜索树的累加

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

二叉搜索树的增删查

二叉搜索树中的插入操作
删除二叉搜索树中的节点
二叉搜索树中的搜索

验证是不是二叉搜索树

验证二叉搜索树

求有多少不同的二叉搜索树

不同的二叉搜索树
不同的二叉搜索树 II

乐高组合范例

二叉搜索子树的最大键值和

二叉搜索树（Binary Search Tree，BST）

首先，BST 的特性大家应该都很熟悉了：

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

2、对于 BST 的每一个节点 node，它的左侧子树和右侧子树都是 BST。

二叉搜索树并不算复杂，直接基于 BST 的数据结构有 AVL 树，红黑树等等，拥有了自平衡性质，可以提供 logN 级别的增删查改效率；还有 B+ 树，线段树等结构都是基于 BST 的思想来设计的。

从做算法题的角度来看 BST，除了它的定义，还有一个重要的性质：BST 的中序遍历结果是有序的（升序）

二叉搜索树转链表

二叉搜索树转链表，之后再操作，对比二叉树转链表，多的一个特性就是中序遍历是有序的。

模板类似于二叉树的转换，不过是把 Queue 换成 ArrayList

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

// https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/
// 中序遍历，把值放入 list 表中，再取出对应的值，粗鄙版本
class Solution {
    ArrayList<Integer> list = new ArrayList<>();

    public int kthSmallest(TreeNode root, int k) {
        traverse(root);
        return list.get(k - 1);
    }

    void traverse(TreeNode root) {
        if (root == null) return ;
        traverse(root.left);
        list.add(root.val);
        traverse(root.right);
    }
}
// 优雅版本
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        list = traverse(root, list);
        return list.get(k - 1);
    }

    ArrayList<Integer> traverse(TreeNode root, ArrayList<Integer> list) {
        if (root == null) return list;
        traverse(root.left, list);
        list.add(root.val);
        traverse(root.right, list);
        return list;
    }
}

// 进阶版，粗鄙版本，达到添加就早停
class Solution {
    int count = 0;
    int res;

    public int kthSmallest(TreeNode root, int k) {
        traverse(root, k);
        return res;
    }

    void traverse(TreeNode root, int k) {
        if (root == null) return ;
        traverse(root.left, k);
        count ++;
        if (count == k) res = root.val;
        else traverse(root.right, k);
        return ;
    }
}
// 优雅版本没想出来

// 迭代，先将左子树压入栈，再判断是否达到条件，不满足条件从最下面节点再压入右子树，比较难想出来
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        while (true) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (--k == 0) return root.val;
            root = root.right;
        }
    }
}

二叉搜索树的累加

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

// https://leetcode-cn.com/problems/convert-bst-to-greater-tree/
// 粗鄙版本
class Solution {
    int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        traverse(root);
        return root;
    }

    void traverse(TreeNode root) {
        if (root == null) return ;
        traverse(root.right);
        root.val = root.val + sum;
        sum = root.val;
        traverse(root.left);
    }
}
// 优雅版本
class Solution {
    public TreeNode convertBST(TreeNode root) {
        traverse(root, 0);
        return root;
    }

    int traverse(TreeNode root, int sum) {
        if (root == null) return sum;
        // 获取右子树（最左边）的 sum
        int right = traverse(root.right, sum);
        // 更新节点的值
        root.val += right;
        // 为了代码一致加的
        sum = root.val;
        // 这里需要注意下，按照题意，函数要返回的值应该是也就是上一个次元需要的值，应该是本节点最左边的节点对应的 sum，还是粗鄙版本好些，果然优雅都是大佬的事情
        int left = traverse(root.left, sum);
        return left;
    }
}
// https://leetcode-cn.com/problems/convert-bst-to-greater-tree/solution/ba-er-cha-sou-suo-shu-zhuan-huan-wei-lei-jia-sh-14/ 评论热评

二叉搜索树的增删查

二叉搜索树中的插入操作

// https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/
//如果该子树不为空，则问题转化成了将 val 插入到对应子树上。
//否则，在此处新建一个以 val 为值的节点，并链接到其父节点 root 上
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        if (val > root.val) {
            root.right = insertIntoBST(root.right, val);
        } else {
            root.left = insertIntoBST(root.left, val);
        }
    }
}
// https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/solution/er-cha-sou-suo-shu-zhong-de-cha-ru-cao-zuo-by-le-3/

删除二叉搜索树中的节点

// https://leetcode-cn.com/problems/delete-node-in-a-bst/
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {//3.递归终止条件
			return null;
		}
		if (key > root.val) {//4.如果查找的结点比根节点大，继续在右子树查找删除该结点
			root.right = deleteNode(root.right, key);
		} else if (key < root.val) {//5.如果查找的结点比根节点小，继续在左子树查找删除该结点
			root.left = deleteNode(root.left, key);
		} else {//6.如果找到了该结点，删除它
			if (root.left == null && root.right == null) {//7.以叶子节点为根节点的二叉搜索树只有一个元素，可以直接删除。
				root = null;
			} else if (root.left == null) {//8.如果有右子树，只要找到该右子树的最小值来替换，之后将它删除即可。
				root.val = rightMin(root);
				root.right = deleteNode(root.right, root.val);//9.将这个右子树的最小值替换根节点，此时存在两个相同节点，将这个节点删除即可。
			} else {//10.如果有左子树，只要找到该左子树的最大值来替换，之后将它删除即可。
				root.val = leftMax(root);
				root.left = deleteNode(root.left, root.val);//9.将这个左子树的最大值替换根节点，此时存在两个相同节点，将这个节点删除即可。
			}
		}
		return root;
    }
    
    public int rightMin(TreeNode root) {//1.找到以某个结点为根节点的右子树最小值。
		root = root.right;
		while (root.left != null) root = root.left;
		return root.val;
	}

	public int leftMax(TreeNode root) {//2.找到以某个结点为根节点的左子树最大值。
		root = root.left;
		while (root.right != null) root = root.right;
		return root.val;
	}
}
// https://leetcode-cn.com/problems/delete-node-in-a-bst/solution/shan-chu-er-cha-sou-suo-shu-zhong-de-jie-dian-by-l/ 评论热评

二叉搜索树中的搜索

// https://leetcode-cn.com/problems/search-in-a-binary-search-tree/
// 递归
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) return root;
        if (val > root.val) {
            return searchBST(root.right, val);
        } else {
            return searchBST(root.left, val);
        }
    }
}
// https://leetcode-cn.com/problems/search-in-a-binary-search-tree/solution/er-cha-sou-suo-shu-zhong-de-sou-suo-by-leetcode/

// 迭代
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while (root != null && root.val != val) {
            root = root.val < val ? root.right : root.left;
        }
        return root;
    }
}

验证是不是二叉搜索树

有两种做法，第一种是验证树的值是否在一个区间内；第二种做法是中序遍历，看是不是递增的

验证二叉搜索树

// https://leetcode-cn.com/problems/validate-binary-search-tree/
// 递归，判断子树的值是否在一个区间内
class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    boolean helper(TreeNode root, long lower, long upper) {
        if (root == null) return true;
        if (root.val <= lower || root.val >= upper) {
            return false;
        }
        return helper(root.left, lower, root.val) && helper(root.right, root.val, upper);
    }
}
// https://leetcode-cn.com/problems/validate-binary-search-tree/solution/yan-zheng-er-cha-sou-suo-shu-by-leetcode-solution/

// 中序遍历
class Solution {
    long pre = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        return inorder(root);
    }

    boolean inorder(TreeNode root) {
        if (root == null) return true;
        boolean left = inorder(root.left);
        if (root.val <= pre) return false;
        pre = root.val;
        boolean right = inorder(root.right);
        return left && right;
    }
}
// 评论

求有多少不同的二叉搜索树

不同的二叉搜索树

// https://leetcode-cn.com/problems/unique-binary-search-trees/
// DP
// 这里的 G[0]=1 表示，在后续的算 F(i,n) 中，左子树或者右子树为空也算一种情况
// G[1]=1 表示，只有单个结点
class Solution {
    public int numTrees(int n) {
        int[] G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;
        for (int i = 2; i <= n; i ++) {
            for (int j = 1; j <= i; j ++) {
                G[i] += G[j - 1] * G[i - j];
            }
        }
        return G[n];
    }
}
// https://leetcode-cn.com/problems/unique-binary-search-trees/solution/bu-tong-de-er-cha-sou-suo-shu-by-leetcode-solution/

不同的二叉搜索树 II

// https://leetcode-cn.com/problems/unique-binary-search-trees-ii/
// 递归获得所有可行的左子树和可行的右子树，最后一步只要从可行左子树集合中选一棵，再从可行右子树集合中选一棵拼接到根节点上，并将生成的二叉搜索树放入答案数组即可。
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) return new LinkedList<TreeNode>();
        return helper(1, n);
    }

    List<TreeNode> helper(int start, int end) {
        List<TreeNode> allTrees = new LinkedList<>();
        if (start > end) {
            allTrees.add(null);
            return allTrees;
        }
        for (int i = start; i <= end; i ++) {
            List<TreeNode> leftTrees = helper(start, i - 1);
            List<TreeNode> rightTrees = helper(i + 1, end);
            for (TreeNode left : leftTrees) {
                for (TreeNode right : rightTrees) {
                    TreeNode currTree = new TreeNode(i);
                    currTree.left = left;
                    currTree.right = right;
                    allTrees.add(currTree);
                }
            }
        }
        return allTrees;
    }
}
// https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/bu-tong-de-er-cha-sou-suo-shu-ii-by-leetcode-solut/

乐高组合范例

二叉搜索子树的最大键值和

// https://leetcode-cn.com/problems/maximum-sum-bst-in-binary-tree/)
// 先判断是不是 BST，再求 BST 和，再进行比较求出最大键值和
class Solution {
    int maxSum = 0;

    public int maxSumBST(TreeNode root) {
        helper(root);
        return maxSum;
    }

    void helper(TreeNode root) {
        if (isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE)) {
            sumNodeValue(root);
            return ;
        }
        helper(root.left);
        helper(root.right);
    }

    int sumNodeValue(TreeNode root) {
        if (root == null) return 0;
        int left = sumNodeValue(root.left);
        int right = sumNodeValue(root.right);
        int sum = left + right + root.val;
        if (sum > maxSum) {
            maxSum = sum;
        }
        return sum;
    }

    boolean isBST(TreeNode root, int min, int max) {
        if (root == null) return true;
        if (root.val <= min || root.val >= max) return false;
        return isBST(root.left, min, root.val) && isBST(root.right, root.val, max);
    }
}

Reference：

https://labuladong.gitee.io/algo/

https://leetcode-cn.com/problems/