黑豆的博客

# 什么是二叉搜索树

满足以下任意条件的树就是二叉搜索树：

  1. 是一颗空树
  2. 由根节点、左子树、右子树组成，并且左子树右子树都是二叉搜索树。且左子树上所有结点的数据域都小于等于根结点的数据域，右子树上所有结点的数据域都大于等于根结点的数据域。

二叉搜索树强调数据域的有序性，每一个颗子树都要满足 左孩子 <= 根节点 <= 右孩子。示例：

    4
   /
  3
 /
2

  5
 / \
2   7
 \
  3

     6
   /   \
  3     8
 / \   / \
1   4 7   9

二叉树的中序遍历是有序的。

const root = {
    val: 6,
    left: {
        val: 3,
        left: {
            val: 1
        },
        right: {
            val: 4
        }
    },
    right: {
        val: 8,
        left: {
            val: 7
        },
        right: {
            val: 9
        }
    }
};

function inorder(root) {
  if (!root) return root;
  inorder(root.left);
  console.log(root.val);
  inorder(root.right);
  return root;
}

inorder(root);
/* 
1
3
4
6
7
8
9
*/

# 二叉搜索树基本操作

# 查找某一特定的值

const root = {
    val: 6,
    left: {
        val: 3,
        left: {
            val: 1
        },
        right: {
            val: 4
        }
    },
    right: {
        val: 8,
        left: {
            val: 7
        },
        right: {
            val: 9
        }
    }
}
function search(root, n) {
  let target = null;
  if (!root) return root;
  if (root.val === n) {
    target = root.val;
  }else if(root.val > n) {
    target = search(root.left, n);
  }else {
    target = search(root.right, n);
  }
  return target;
}

# 插入新节点

const root = {
    val: 6,
    left: {
        val: 3,
        left: {
            val: 1
        },
        right: {
            val: 4
        }
    },
    right: {
        val: 8,
        left: {
            val: 7
        },
        right: {
            val: 9
        }
    }
}

function insert(root, n) {
  if (!root) {
    root = new TreeNode(n);
    return root;
  }
  if (root.val > n) {
    root.left = insert(root.left, n);
  }else {
    root.right = insert(root.right, n);
  }
  return root;
}

function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}

# 删除某一节点

function deleteNode(root, key) {
  if (!root) return null;
  if (root.val === key) {
      if (!root.left) return root.right;
      if (!root.right) return root.left;

      let node = root.right;
      while (node.left) {
          node = node.left;
      }
      node.left = root.left;
      root = root.right;
  }else if (root.val > key) {
      root.left = deleteNode(root.left, key);
  }else {
      root.right = deleteNode(root.right, key);
  }
  return root;
}

# 二叉搜索树的验证

题目描述：给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:

  2
 / \
1   3

输出: true

示例 2:

  5
 / \
1   4
   / \
  3   6

输出: false

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

方法一：

const isValidBST = function(root) {
  function dfs(root, minValue, maxValue) {
    if !(root) {
      return true;
    }
    if (root.val <= minValue || root.val >= maxValue) return false;
    return dfs(root.left, minValue, root.val) && dfs(root.right, root.val, maxValue)
  }
  return dfs(root, -Infinity, Infinity)
}

方法二：

var isValidBST = function (root) {
    let minValue = -Infinity;
    function inorder(root) {
        if (!root) return true;
        if (!inorder(root.left)) return false;
        if (root.val <= minValue) return false;
        minValue = root.val;
        return inorder(root.right);
    }
    return inorder(root);
};

# 将排序数组转为二叉搜索树

题目描述：将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

方式一：

var sortedArrayToBST = function (nums) {
    const root = buildBST(nums);
    function buildBST(nums) {
        const len = nums.length;
        if (!len) return null;
        const mid = Math.floor(len / 2);
        const cur = new TreeNode(nums[mid]);
        cur.left = buildBST(nums.slice(0, mid))
        cur.right = buildBST(nums.slice(mid + 1));
        return cur;
    }
    return root;
};

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

方式二：

var sortedArrayToBST = function (nums) {
    const root = buildBST(0, nums.length - 1);

    function buildBST(low, high) {
        if (low > high) return null;
        const mid = Math.floor((low + high) / 2);
        const cur = new TreeNode(nums[mid]);
        cur.left = buildBST(low, mid - 1);
        cur.right = buildBST(mid + 1, high);
        return cur;
    }
    return root;
};

← 平衡二叉树 →