二叉搜索树

二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。

示例 1:

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

递归

public TreeNode searchBST(TreeNode root, int val) {
    if (root == null) {
        return null;
    }
    if (root.val == val) {
        return root;
    }
    return searchBST(root.val < val ? root.right : root.left, val);
}

迭代

public TreeNode searchBST(TreeNode root, int val) {
    while (root != null) {
        if (root.val == val) {
            return root;
        } 
        root = root.val < val ? root.right : root.left;
    }
    return null;
}

二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第k大的节点。

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4

限制：

1 ≤ k ≤ 二叉搜索树元素个数

右根左

private TreeNode node;

private int i;

public int kthLargest(TreeNode root, int k) {
    postorder(root, k);
    return node.val;
}

public void postorder(TreeNode root, int k) {
    if (root != null) {
        postorder(root.right, k);
        i++;
        if (i == k) {
            node = root;
        }
        postorder(root.left, k);
    }
}

验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4

错误的思路：
根大于左子树，小于右子树，再递归判断左右子树
原因：不仅跟要大于右子树，而且要大于右子树的所有节点

方法一：递归（上下界）

判断左子树时将根作为上界，判断右子树时将根作为下界

public boolean isValidBST(TreeNode root) {
    return recurse(root, null, null);
}

public boolean recurse(TreeNode root, Integer lower, Integer supper) {
    if (root == null) {
        return true;
    }
    if (lower != null && root.val <= lower) {
        return false;
    }
    if (supper != null && root.val >= supper) {
        return false;
    }
    return recurse(root.left, lower, root.val) && recurse(root.right, root.val, supper);
}

迭代实现：

private Stack<TreeNode> stack = new Stack<>();
private Stack<Integer> lowers = new Stack<>();
private Stack<Integer> suppers = new Stack<>();

public boolean isValidBST(TreeNode root) {
    if (root == null) {
        return true;
    }
    Integer lower = null;
    Integer supper = null;
    update(root, lower, supper);
    while (!stack.isEmpty()) {
        root = stack.pop();
        lower = lowers.pop();
        supper = suppers.pop();
        if (lower != null && root.val <= lower) {
            return false;
        }
        if (supper != null && root.val >= supper) {
            return false;
        }
        if (root.left != null) {
            update(root.left, lower, root.val);
        }
        if (root.right != null) {
            update(root.right, root.val, supper);
        }
    }
    return true;
}

public void update(TreeNode root, Integer lower, Integer supper) {
    stack.push(root);
    lowers.add(lower);
    suppers.add(supper);
}

方法二：中序遍历

private Integer pre = null;

public boolean isValidBST(TreeNode root) {
    if (root == null) {
        return true;
    }
    if (!isValidBST(root.left)) {
        return false;
    }
    if (pre !=null && root.val <= pre) {
        return false;
    }
    pre = root.val;
    return isValidBST(root.right);
}

迭代法：

public boolean isValidBST(TreeNode root) {
    if (root == null) {
        return true;
    }
    Integer pre = null;
    Stack<TreeNode> stack = new Stack<>();
    while (!stack.isEmpty() || root != null) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        if (pre != null && root.val <= pre) {
            return false;
        }
        pre = root.val;
        root = root.right;
    }
    return true;
}

二叉搜索树的最小绝对差

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

输入：root = [4,2,6,1,3]
输出：1

递归
中序遍历

int min = Integer.MAX_VALUE;
int pre = -1;

public int getMinimumDifference(TreeNode root) {
    dfs(root);
    return min;
}

private void dfs(TreeNode root) {
    if (root == null) {
        return;
    }
    dfs(root.left);
    if (pre != -1) {
        min = Math.min(min, root.val - pre);
    }
    pre = root.val;
    dfs(root.right);
}

迭代

public int getMinimumDifference(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode pre = null;
    int min = Integer.MAX_VALUE;
    while (!stack.isEmpty() || root != null) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        if (pre != null) {
            min = Math.min(min, root.val - pre.val);
        }
        pre = root;
        root = root.right;
    }
    return min;
}

二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树

示例 1：

输入：root = [1,null,2,2]
输出：[2]

如果不是二叉搜索树，遍历树，统计每一数字的出现次数，最后对出现次数做排序，取最大的。
由于二叉搜索树，中序遍历是非递减的序列，所以在遍历过程中不断更新每一个数的出现次数并取最大的

递归

private TreeNode pre;
private int count, maxCount;
private List<Integer> res = new ArrayList<>();

public int[] findMode(TreeNode root) {
    dfs(root);
    return res.stream().mapToInt(num -> num).toArray();
}

private void dfs(TreeNode root) {
    if (root == null) {
        return;
    }
    dfs((root.left));
    if (pre == null || pre.val == root.val) {
        count++;
    } else {
        count = 1;
    }
    if (count > maxCount) {
        maxCount = count;
        res.clear();
        res.add(root.val);
    } else if (count == maxCount) {
        res.add(root.val);
    }
    pre = root;
    dfs(root.right);
}

迭代

public int[] findMode(TreeNode root) {
    TreeNode pre = null;
    int count = 0, maxCount = 0;
    List<Integer> res = new ArrayList<>();

    Stack<TreeNode> stack = new Stack<>();
    while (!stack.isEmpty() || root != null) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        if (pre == null || pre.val == root.val) {
            count++;
        } else {
            count = 1;
        }
        if (count > maxCount) {
            maxCount = count;
            res.clear();
            res.add(root.val);
        } else if (count == maxCount) {
            res.add(root.val);
        }
        pre = root;
        root = root.right;
    }
    return res.stream().mapToInt(num -> num).toArray();
}

二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。保证原始二叉搜索树中不存在新值。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。

例如,

给定二叉搜索树:
        4
       / \
      2   7
     / \
    1   3
和 插入的值: 5

你可以返回这个二叉搜索树:

         4
       /   \
      2     7
     / \   /
    1   3 5

或者这个树也是有效的:
         5
       /   \
      2     7
     / \   
    1   3
         \
          4

方法一：递归

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

方法二：迭代

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

删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 **root **和一个值 key，删除二叉搜索树中的 **key **对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。

示例 1:

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

递归
这里有三种可能的情况：

要删除的节点为叶子节点，可以直接删除。
要删除的节点不是叶子节点且拥有右节点，则该节点可以由该节点的后继节点进行替代，该后继节点位于右子树中较低的位置。然后可以从后继节点的位置递归向下操作以删除后继节点。
要删除的节点不是叶子节点，且没有右节点但是有左节点。这意味着它的后继节点在它的上面，但是我们并不想返回。我们可以使用它的前驱节点进行替代，然后再递归的向下删除前驱节点。

算法：

如果 key > root.val，说明要删除的节点在右子树，root.right = deleteNode(root.right, key)。
如果 key < root.val，说明要删除的节点在左子树，root.left = deleteNode(root.left, key)。
如果 key == root.val，则该节点就是我们要删除的节点，则：
- 如果该节点是叶子节点，则直接删除它：root = null。
- 如果该节点不是叶子节点且有右节点，则用它的后继节点的值替代 root.val = successor.val，然后删除后继节点。
- 如果该节点不是叶子节点且只有左节点，则用它的前驱节点的值替代 root.val = predecessor.val，然后删除前驱节点。

public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) {
        return null;
    }
    if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else {
        if (root.left == null && root.right == null) {
            root = null;
        } else if (root.right != null) {
            root.val = successor(root);
            root.right = deleteNode(root.right, root.val);
        } else {
            root.val = predecessor(root);
            root.left = deleteNode(root.left, root.val);
        }
    }
    return root;
}

// 后继结点为中序遍历后一个结点，即先切到右子树，再遍历左子树
private int successor(TreeNode root) {
    root = root.right;
    while (root.left != null) {
        root = root.left;
    }
    return root.val;
}

// 前继结点为中序遍历前一个结点，即先切到左子树，再遍历右子树
private int predecessor(TreeNode root) {
    root = root.left;
    while (root.right != null) {
        root = root.right;
    }
    return root.val;
}

另外的思路：
找到key结点后

有一棵子树为空，返回非空子树
否则将前继结点或后继结点替换

public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) {
        return null;
    }
    if (root.val == key) {
        if (root.right == null) {
            return root.left;
        } else {
            // 这里是将后继结点替换，也可以改成用前继结点替换
            TreeNode cur = root.right;
            while (cur.left != null) {
                cur = cur.left;
            }
            int val = root.val;
            root.val = cur.val;
            cur.val = val;
            root.right = deleteNode(root.right, key);
        }
    } else if (root.val > key) {
        root.left = deleteNode(root.left, key);
    } else {
        root.right = deleteNode(root.right, key);
    }
    return root;
}

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

示例 1：

输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]

方法一：递归

public TreeNode trimBST(TreeNode root, int low, int high) {
    if (root == null) {
        return null;
    }
    // 根及左子树所有都小，全部抛弃，取右子树
    if (root.val < low) {
        return trimBST(root.right, low, high);
    }
    // 根及右子树所有都大，全部抛弃，取左子树
    if (root.val > high) {
        return trimBST(root.left, low, high);
    }
    // 根满足条件，裁剪它们的子树
    root.left = trimBST(root.left, low, high);
    root.right = trimBST(root.right, low, high);
    return root;
}

迭代

public TreeNode trimBST(TreeNode root, int low, int high) {
    if (root == null) {
        return null;
    }
    // 从根开始二分找到一个满足条件的结点
    while (root != null) {
        if (root.val < low) {
            root = root.right;
        } else if (root.val > high) {
            root = root.left;
        } else {
            break;
        }
    }
    // 处理左子树小于的结点
    TreeNode cur = root;
    while (cur != null) {
        // 如果左子树的根结点都小于，直接将 右子树挂过来
        while (cur.left != null && cur.left.val < low) {
            cur.left = cur.left.right;
        }
        cur = cur.left;
    }
    cur = root;
    while (cur != null) {
        // 如果左子树的根结点都小于，直接将 右子树挂过来
        while (cur.right != null && cur.right.val > high) {
            cur.right = cur.right.left;
        }
        cur = cur.right;
    }  
    return root;
}

将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵 高度平衡 二叉搜索树。
**高度平衡 **二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

递归
中序遍历，取一个做根结点，两边做左右子树

public TreeNode sortedArrayToBST(int[] nums) {
    return build(nums, 0, nums.length - 1);
}

public TreeNode build(int[] nums, int low, int high) {
    if (low > high) {
        return null;
    }
    // 选取中间位置的左边做根结点
    // 也可以选取中间位置的右边做根结点：int mid = (low + high + 1) / 2;
    // 也可以随机选择一个做根结点：int mid = (low + high + rand.nextInt(2)) / 2;
    int mid = (low + high) / 2;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = build(nums, low, mid - 1);
    root.right = build(nums, mid + 1, high);
    return root;
}

迭代

public TreeNode sortedArrayToBST(int[] nums) {
    if (nums == null || nums.length == 0) {
        return null;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    Queue<int[]> posQueue = new LinkedList<>();
    TreeNode root = new TreeNode(0);
    queue.add(root);
    posQueue.add(new int[]{0, nums.length - 1});
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        int[] pair = posQueue.poll();
        int mid = (pair[0] + pair[1]) / 2;
        node.val = nums[mid];
        if (mid - 1 >= pair[0]) {
            node.left = new TreeNode(0);
            queue.add(node.left);
            posQueue.add(new int[]{pair[0], mid - 1});
        }
        if (mid + 1 <= pair[1]) {
            node.right = new TreeNode(0);
            queue.add(node.right);
            posQueue.add(new int[]{mid + 1, pair[1]});
        }
    }
    return root;
}

将二叉搜索树变平衡

给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。
如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。

如果有多种构造方法，请你返回任意一种。

示例：

输入：root = [1,null,2,null,3,null,4,null,null]
输出：[2,1,3,null,null,null,4]
解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。

贪心构造
「平衡」要求它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，这很容易让我们产生这样的想法——左右子树的大小越「平均」，这棵树会不会越平衡？于是一种贪心策略的雏形就形成了：我们可以通过中序遍历将原来的二叉搜索树转化为一个有序序列，然后对这个有序序列递归建树，对于区间 [L, R][：

取mid即中心位置作为当前节点的值；
[L,mid−1] 作为当前节点的左子树；
[mid+1,R] 作为当前节点的右子树。

private List<TreeNode> list = new ArrayList<>();

public TreeNode balanceBST(TreeNode root) {
    inorder(root);
    return build(0, list.size() - 1);
}

private void inorder(TreeNode root) {
    if (root == null) {
        return;
    }
    inorder(root.left);
    list.add(root);
    inorder(root.right);
}

private TreeNode build(int low, int high) {
    if (low > high) {
        return null;
    }
    int mid = (low + high) / 2;
    TreeNode root = list.get(mid);
    root.left = build(low, mid - 1);
    root.right = build(mid + 1, high);
    return root;
}

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

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如：

输入: 原始二叉搜索树:
              5
            /   \
           2     13

输出: 转换为累加树:
             18
            /   \
          20     13

递归

private TreeNode pre;

public TreeNode bstToGst(TreeNode root) {
    if (root == null) {
        return null;
    }
    bstToGst(root.right);
    if (pre != null) {
        root.val += pre.val;
    }
    pre = root;
    bstToGst(root.left);
    return root;
}

迭代

public TreeNode convertBST(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode pre = null;
    TreeNode node = root;
    while (!stack.isEmpty() || node != null) {
        while (node != null) {
            stack.add(node);
            node = node.right;
        }
        node = stack.pop();
        if (pre != null) {
            node.val += pre.val;
        }
        pre = node;
        node = node.left;
    }
    return root;
}

二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

示例 1：

输入: [1,6,3,2,5]
输出: false

示例 2：

输入: [1,3,2,6,5]
输出: true

递归
划分左右子树：数组最右边的元素为根，向前找到第一个大于根的位置，即为右子树部分，剩下部分为左子树

public boolean verifyPostorder(int[] postorder) {
    return dfs(postorder, 0, postorder.length - 1);
}

private boolean dfs(int[] postorder, int low, int high) {
    // 只有一个元素时肯定满足
    if (low >= high) {
        return true;
    }
    // 从最后的前一个位置开始向前遍历，找到第一个小于根的元素
    // 如果合法，左边部分就是左子树，右边部分就是右子树
    int index = high - 1;
    while (index >= low && postorder[index] > postorder[high]) {
        index--;
    }
    // 判断是否合法：即判断左子树是否全部小于根
    for (int i = index; i >= low; i--) {
        if (postorder[i] >= postorder[high]) {
            return false;
        }
    }
    return dfs(postorder, low, index) && dfs(postorder, index + 1, high - 1);
}

单调栈
维护一个升序的栈

后续遍历结果是
[3,6,5,9,8,11,13,12,10]

如果两个挨着的是，arr[i] < arr[i - 1]，则arr[i - 1]一定是arr[i]的右孩子
如果arr[i] > arr[i - 1]，可能arr[i]作为右子树或者根节点更大，所以arr[i - 1]一定是arr[i]...arr[n]某个结点的左孩子，又由于右结点比根大，所以根结点是arr[i]...arr[n]中最小的结点

根据上面分析的过程，很容易想到使用栈来解决。遍历数组的所有元素，如果栈为空，就把当前元素压栈。如果栈不为空，并且当前元素大于栈顶元素，说明是升序的，那么就说明当前元素是栈顶元素的右子节点，就把当前元素压栈，如果一直升序，就一直压栈。当前元素小于栈顶元素，说明是倒序的，说明当前元素是某个节点的左子节点，我们目的是要找到这个左子节点的父节点，就让栈顶元素出栈，直到栈为空或者栈顶元素小于当前值为止，其中最后一个出栈的就是当前元素的父节点

public boolean verifyPostorder(int[] postorder) {
    Stack<Integer> stack = new Stack<>();
    int root = Integer.MAX_VALUE;
    for (int i = postorder.length - 1; i >= 0; i--) {
        // 如果当前元素比之前的小，说明当前元素是之前出现最小元素的左子树
        while (!stack.isEmpty() && postorder[i] < stack.peek()) {
            root = stack.pop();
        }
        // 如果是二叉搜索树，不可能比root大：
        // root为上一次有左子树的根，数组前面的为根的左子树，所以不会大于根
        if (postorder[i] > root) {
            return false;
        }
        stack.push(postorder[i]);
    }
    return true;
}

不同的二叉搜索树

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3
输出: 5
解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

动态规划

假设n个节点存在二叉排序树的个数是G(n)，令f(i)为以i为根的二叉搜索树的个数
G(n) = f(1) + f(2) + ... + f(n)

当i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i，则
f(i) = G(i-1)*G(n-i)

综合两个公式可以得到卡特兰数公式
G(n) = G(0)×G(n-1)+G(1)×(n-2)+...+G(n-1)×G(0)

public int numTrees(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }
    return dp[n];
}

G(n)函数的值在数学上被称为卡塔兰数
C₀=1
C_n+1=C_n×2×(2n+1)/(n+2)

public int numTrees(int n) {
    // 提示：我们在这里需要用 long 类型防止计算过程中的溢出
    long C = 1;
    for (int i = 0; i < n; ++i) {
        C = C * 2 * (2 * i + 1) / (i + 2);
    }
    return (int) C;
}