[数据结构]二叉树 - [数据结构]二叉搜索树 - 《数据结构与算法》

二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（Ordered Binary Tree）或排序二叉树（Sorted Binary Tree），是指一棵空树或者具有下列性质的二叉树：

节点的左子树只包含键值小于节点键值的节点。
节点的右子树只包含键值大于节点键值的节点。
左右子树也必须是二叉搜索树。
没有键值相等的节点。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低, 为O(logn)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。

二叉查找树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉查找树的存储结构。中序遍历二叉查找树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉查找树变成一个有序序列，构造树的过程即为对无序序列进行查找的过程。每次插入的新的结点都是二叉查找树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索、插入、删除的复杂度等于树高，期望 O(logn)，最坏O(n)（数列有序，树退化成线性表）。

然二叉查找树的最坏效率是 O(n)，但它支持动态查询，且有很多改进版的二叉查找树可以使树高为 O(logn)，从而将最坏效率降至 O(logn)，如 AVL 树、红黑树等。

95. 不同的二叉搜索树 II

function generateTrees(n: number): Array<TreeNode | null> {
    if (n == 0) return [];
    return helper(1, n);
};
function helper (start: number, end: number): Array<TreeNode | null> {
    let ans = [];
    if (start > end) {
        ans.push(null);
        return ans;
    }
    for (let i = start; i <= end; i++) {
        let lefts = helper(start, i - 1);
        let rights = helper(i + 1, end);
        for (let left of lefts) {
            for (let right of rights) {
                let root = new TreeNode(i);
                root.left = left;
                root.right = right;
                ans.push(root);
            }
        }
    }
    return ans;
}

练习1: 递归

98. 验证二叉搜索树

节点的左子树只包含小于当前节点的数。 ⚠️ 仅比较当前节点、左节点、右节点不全面。需要辅助函数

var isValidBST = function(root) {
    return compareBST(root, -Infinity, Infinity)
};

function compareBST(root, min, max) {
    if (root == null) return true;
    let cur = root.val;
    if (min >= cur || max <= cur) return false;
    return compareBST(root.left, min, cur) && compareBST(root.right, cur, max)
}

错误写法

var isValidBST = function(root) {
    if (root == null) return true;
    if (root.left != null && root.left.val >= root.val) return false;
    if (root.right != null && root.right.val <= root.val) return false;
    return isValidBST(root.left) && isValidBST(root.right);
};

测试用例

   5
  / \
 4   6
    / \
   3   7
输出： false
解释： 4 比 3 大

剑指 Offer 33. 二叉搜索树的后序遍历序列

var verifyPostorder = function(postorder) {
    // [left, right, mid]
    return helper(postorder, 0, postorder.length - 1);
};

function helper(postorder, left, right) {
    if (left >= right) return true;
    let val = postorder[right];

    let index = left;
    // 右子树的序列开始位置
    while (postorder[index] < val) {
        index++;
    }
    // console.log(left, right, index)
    // 出口
    for (let i = index+1; i<right; i++) {
        if (postorder[i] < val) return false;
    }
    return helper(postorder, left, index-1) && helper(postorder, index, right - 1)
}

700.二叉搜索树中的搜索

var searchBST = function(root, val) {
    if (!root) return null;
    if (root.val == val) return root;
    else if (root.val > val) return searchBST(root.left, val);
    else return searchBST(root.right, val);
};

235. 二叉搜索树的最近公共祖先（剑指 Offer 68 - I. 二叉搜索树的最近公共祖先）

终止条件（无）
递归条件
- 全部在左子树
- 全部在右子树

返回值（根）

var lowestCommonAncestor = function(root, p, q) {
      // 范围缩小至左子树
  if (p.val < root.val && q.val < root.val) {
      return lowestCommonAncestor(root.left, p, q)
  }
      // 范围缩小到右子树
  if (p.val > root.val && q.val > root.val) {
      return lowestCommonAncestor(root.right, p, q)
  }

  return root;
};

练习2: 遍历

538. 把二叉搜索树转换为累加树（1038. 把二叉搜索树转换为累加树）

var convertBST = function(root) {
  // 后  中  前
  var dfs = function(root) {
      if (root == null) return;
      dfs(root.right)
      sum = sum + root.val
      root.val = sum
      dfs(root.left)
  }
  var sum = 0
  dfs(root)
  return root
};

230. 二叉搜索树中第K小的元素 (剑指 Offer 54. 二叉搜索树的第k大节点)

方法1（推荐）：从小到达访问节点
优点：不必遍历所有节点。深度优先，使用栈暂存节点

var kthSmallest = function(root, k) {
  let stack = [];
  while (true) {
      while (root) {
          stack.push(root);
          root = root.left;
      }
      root = stack.pop();
      k -= 1;
      if (k == 0) return root.val;
      root = root.right;
  }
};

方法2：中序遍历

var kthSmallest = function(root, k) {
    // 中序遍历
    let arr = inorder(root);
    // console.log(arr, k);
    return arr[k -1];
};

function inorder(root) {
    if (root == null) return [];
    return [...inorder(root.left), root.val, ...inorder(root.right)]
}

练习3: 操作二叉树

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

function sortedArrayToBST(nums: number[]): TreeNode | null {
    return createBST(nums, 0, nums.length -1);
};

function createBST(nums: number[], left: number, right: number) {
    if (left > right) return null;
    let mid = (left + right) >> 1;
    let root = new TreeNode(nums[mid]);
    root.left = createBST(nums, left, mid - 1);
    root.right = createBST(nums, mid + 1, right);
    return root;
}

解释

[-10,-3,0,5,9]

     0
    / \
  -10  5
    \   \
    -3   9
let mid = Math.floor((left + right) / 2); // 右边优先填充

     0
    / \
  -3   9
  /    /
-10    5
let mid = Math.ceil((left + right) / 2); // 左边优先填充

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

function sortedListToBST(head: ListNode | null): TreeNode | null {
    let nums = [];
    while (head != null) {
        nums.push(head.val);
        head = head.next;
    }
    return createBST(nums, 0, nums.length - 1);
};

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

var insertIntoBST = function(root, val) {
    if (!root) return new TreeNode(val);
    if (root.val < val) root.right = insertIntoBST(root.right, val);
    if (root.val > val) root.left = insertIntoBST(root.left, val);
    return root;
}

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

var deleteNode = function(root, key) {
    if (!root) return null; 
    if (root.val == key) {
        if (!root.left) return root.right;
        if (!root.right) return root.left;
        // 改动tree位置
        const minNode = getMin(root.right);
        root.val = minNode.val;
        root.right = deleteNode(root.right, minNode.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;
};

function getMin (root) {
    while (root.left) root = root.left;
    return root;
}

参考：
https://leetcode-cn.com/tag/binary-search-tree/
https://leetcode-cn.com/leetbook/read/introduction-to-data-structure-binary-search-tree/x6l2am/