这是二叉树的一个品类，搞得不多。
二叉搜索树呢，也多是 中序遍历，这和 二叉树无关，关乎我们对二叉树的进一步认识。

1.有序数组 生成 二叉搜索树

2.有序数组 生成 高度平衡的二叉搜索树

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

109. 有序链表转换二叉搜索树
类似

3.平衡 二叉树 相关

1382. 将二叉搜索树变平衡

借助 108 的解题思路

  1. var balanceBST = function(root) {
  2.     let nums = [];
  4.     function dfs(node) {
  5.         if (!node) {
  6.             return;
  7.         }
  9.         dfs(node.left);
  10.         nums.push(node.val);
  11.         dfs(node.right);
  12.     }
  14.     dfs(root); // 生成有序数组
  16.     let n = nums.length;
  18.     function createTree(left, right) {
  19.         if (left > right) {
  20.             return null;
  21.         }
  23.         let mid = left + Math.floor((right - left) / 2);
  24.         let newNode = new TreeNode(nums[mid]);
  25.         newNode.left = createTree(left, mid - 1);
  26.         newNode.right = createTree(mid + 1, right);
  28.         return newNode;
  29.     }
  31.     return createTree(0, n - 1); // 根据有序数组递归生成平衡树
  32. };

96. 不同的二叉搜索树

根据有序数组生成 二叉搜索树是不唯一的，本题就是数数，但是用到的是动态规划的思路。

  1. var numTrees = function(n) {
  2.     let dp = new Array(n + 1).fill(0);
  3.     dp[0] = 1;
  4.     dp[1] = 1;
  6.     for (let i = 2; i <= n; i++) {
  7.         for (let j = 0; j < i; j++) { 
  8.             dp[i] += dp[j] * dp[i - 1 - j]; // 就是硬找规律
  9.         }
  10.     }
  12.     return dp[n];
  13. };

285. 二叉搜索树中的中序后继

  1. var inorderSuccessor = function(root, p) {
  2.     let target = null;
  3.     let hasfound = false;
  5.     function dfs(node) {
  6.         if (!node) {
  7.             return null;
  8.         }
  10.         // 一开始我把中序遍历的操作 当做条件阻挡放在前序的位置，这样的操作其实很错乱
  11.         // if (hasfound) {
  12.         //     if (target === null) { // 第一次赋值
  13.         //         target = node;
  14.         //     }
  16.         //     return;
  17.         // }
  19.         dfs(node.left);
  21.         // 这是递归返回要一直执行的地方啊
  22.         if (p.val === node.val) {
  23.             hasfound = true;
  24.         } else if (hasfound) {
  25.             if (target === null) { // 第一次赋值
  26.                 target = node;
  27.             }
  29.             return;
  30.         }
  31.         dfs(node.right);
  32.     }
  34.     dfs(root);
  36.     return target;
  37. };

510. Inorder Successor in BST II

  1. var inorderSuccessor = function(node) { // 只能向上走，缺乏向下走的路
  2.     if (node === null) {
  3.         return null;
  4.     }
  6.     // 先找 root 可转化题目为 285 leetcode
  7.     let root = node;
  8.     while (root.parent) { // 找 root
  9.         root = root.parent;
  10.     }
  12.     let hasfound = false;
  13.     let target = null;
  14.     function dfs(n) {
  15.         if (!n) {
  16.             return null;
  17.         }
  19.         dfs(n.left);
  20.         if (n.val === node.val) {
  21.             hasfound = true;
  22.         } else if (hasfound) {
  23.             if (target === null) {
  24.                 target = n; // 大意的错误
  25.             }
  26.             return;
  27.         }
  28.         dfs(n.right);
  29.     }
  31.     dfs(root);
  32.     return target;
  33. };