练习

定义

  • 每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。
  • 每个节点中的值必须小于（或等于）存储在其右子树中的任何值。

模板

  1. function BST(root, target) {
  2.     if (root.val == target)
  3.         // 找到目标，做点什么
  4.     if (root.val < target) 
  5.         BST(root.right, target);
  6.     if (root.val > target)
  7.         BST(root.left, target);
  8. }

应用

validate-binary-search-tree

验证二叉搜索树

  1. var isValidBST = function(root) {
  2.     var helper = function(root, max, min){
  3.         if(root == null) return true;
  4.         if(max !== null && root.val >= max.val) return false;
  5.         if(min !== null && root.val <= min.val) return false;
  6.         return helper(root.left, root,min) && helper(root.right, max, root);
  7.     };
  9.     return helper(root,null,null);
  10. };

insert-into-a-binary-search-tree

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。

  1. var insertIntoBST = function(root, val) {
  2.     if(root == null) {
  3.         return new TreeNode(val)
  4.     } else if (root.val > val) {
  5.         root.left =  insertIntoBST(root.left,val);
  6.     } else {
  7.         root.right = insertIntoBST(root.right, val);
  8.     }
  9.     return root;
  10. };

delete-node-in-a-bst

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

  1. // 注意一下，这个删除操作并不完美，因为我们一般不会通过 root.val = minNode.val 修改节点内部的值来交换节点，
  2. // 而是通过一系列略微复杂的链表操作交换 root 和 minNode 两个节点。因为具体应用中，val 域可能会很大，
  3. // 修改起来很耗时，而链表操作无非改一改指针，而不会去碰内部数据。
  4. var deleteNode = function(root, key) {
  5.     if(root == null) return root;
  6.     if (root.val == key){
  7.         // 找到目标，做点什么
  8.         if(root.left == null) return root.right;
  9.         if(root.right == null ) return root.left;
  10.         // 处理情况 3
  11.         let minNode = getMin(root.right);
  12.         root.val = minNode.val;
  13.         root.right = deleteNode(root.right, minNode.val);
  14.     }
  15.     if (root.val > key) 
  16.         root.left = deleteNode(root.left, key);
  17.     if (root.val < key)
  18.         root.right = deleteNode(root.right, key);
  19.     return root;
  20. };
  22. var getMin = function (node) {
  23.       // BST 最左边的就是最小的
  24.       while (node.left != null) node = node.left;
  25.       return node;
  26. }