二叉搜索树的应用问题

二叉搜索树的定义

• 若左子树不空，则左子树上所有节点的值均小于根节点的值
• 若右子树不空，则右子树上所有节点的值均大于根节点的值
• 它的左右子树也均为二叉搜索树
• 中序遍历结果为一个升序数组

LeeCode 98: 验证二叉搜索树

题目描述

给你一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树。

建立模型

方法一

• 中序遍历二叉树，并将结构保存到数组中
• 判断数组是否为升序

方法二

• 计算每个节点值的可能区间
• 若所有节点值均在区间内，则是一棵有效的二叉搜索树，返回 true
• 若存在节点的值不在所属区间内，则不是一个有效的二叉搜索树 false
• 由于 \(-2^{31} < node.val < 2^{31} - 1\)，所以Integer类型初始最大值不够，需要Long类型

代码实现

// 方法一
public boolean isValidBST(TreeNode root) {
  List<Integer> inorder = new ArrayList<>();

  Stack<TreeNode> stack = new Stack<>();
  TreeNode node = root;
  while (node != null || !stack.isEmpty()) {
    while (node != null) {
      stack.push(node);
      node = node.left;
    }

    node = stack.pop();
    inorder.add(node.val);
    node = node.right;
  }

  // 判断中序遍历是否为升序序列
  for (int i = 0; i < inorder.size() - 1; i++) {
    if (inorder.get(i) >= inorder.get(i + 1)) {
      return false;
    }
  }

  return true;
}

// 方法二
public boolean isValidBST(TreeNode root) {
  return isValidBSTImpl(root, Long.MAX_VALUE, Long.MIN_VALUE);
}

/**
 * @root 当前节点
 * @max 节点值上界
 * @min 节点值下界
 */
public boolean isValidBSTImpl(TreeNode root, long max, long min) {
  if (root == null) {
    return true;
  }
  
  if (root.val >= max || root.val <= min) {
    return false;
  }
  
  return isValidBSTImpl(root.left, root.val, min) && isValidBSTImpl(root.right, max, root.val);
}

LeeCode 235: 二叉搜索树的最近公共祖先

题目描述

给定一个二叉搜索树，找到该树中两个指定节点的最近公共祖先。

建立模型

• 不同于二叉树的最近公共祖先，本题是一棵二叉搜索树
• 可以通过节点值的大小关系来判断存在于左子树还是右子树

代码实现

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  if (root == null || root == p || root == q) {
    return root;
  }

  TreeNode node = null;
  if (p.val < root.val && q.val < root.val) {
    node = lowestCommonAncestor(root.left, p, q);
  }
  else if(p.val > root.val && q.val > root.val) {
    node = lowestCommonAncestor(root.right, p, q);
  }
  else {
    node = root;
  }

  return node;
}

LeeCode 701: 二叉搜索树的插入操作

题目描述

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

建立模型

核心思路：将新增节点插入到对应的空节点

1. 若插入节点值大于当前节点，则递归判断其右子节点
2. 若右子节点为空，则将新增节点插入到当前节点的右边
3. 若插入节点值小于当前节点，则递归判断其左子节点
4. 若左子节点为空，则将新增节点插入到当前节点的左边

代码实现

public TreeNode insertIntoBST(TreeNode root, int val) {
  TreeNode insert = new TreeNode(val);
  if (root == null) {
    return insert;
  }

  TreeNode node = root;
  boolean flag = true;
  while (flag) {
    if (node.val < val) {
      if (node.right == null) {
        node.right = insert;
        flag = false;
      }
      else {
        node = node.right;
      }
    }
    else {
      if (node.left == null) {
        node.left = insert;
        flag = false;
      }
      else {
        node = node.left;
      }
    }
  }

  return root;
}

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

题目描述

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

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

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

建立模型

1. 找到需要删除的节点和它的父节点
2. 若需要删除的节点为父节点的左子节点，则分别讨论需要删除节点的左右子节点是否为空，修改pre.left域，调整树结构
3. 若需要删除的节点为父节点的右子节点，则分别讨论需要删除节点的左右子节点是否为空，修改pre.right域，调整树结构
4. 步骤2，3是一个对称的过程，理解了步骤2也就理解了步骤3

代码实现

public TreeNode deleteNode(TreeNode root, int key) {
  // 创建虚拟根节点，从而可以不需要为处理root节点添加额外的讨论
  TreeNode virtualHead = new TreeNode((int)(Math.pow(10, 5) + 1));
  virtualHead.left = root;

  TreeNode pre = virtualHead;    // 当前节点的父节点
  TreeNode cur = root;    // 当前节点

  while (cur != null) {
    if (cur.val > key) {
      pre = cur;
      cur = cur.left;
    }
    else if (cur.val < key) {
      pre = cur;
      cur = cur.right;
    }
    
    // 当前节点为要删除的节点
    else {
      // 父节点的值大于当前节点，说明需要删除的是左子节点
      if (pre.val > key) {
        // 当前节点的左右子结点均不为空，调整树结构
        // pre -> left 指向 cur.right
        // 查找当前节点右子结点的最左节点，将该节点的left指向cur.left
        if (cur.right != null && cur.left != null) {
          pre.left = cur.right;
          TreeNode node = cur.right;
          while (node.left != null) {
            node = node.left;
          }
          node.left = cur.left;
        }
		
        // 当前节点的右子结点不为空，左子节点为空
        // 则直接将 pre.left 指向 cur.right
        else if (cur.right != null) {
          pre.left = cur.right;
        }
		
        // 当前节点的左子结点不为空，右子节点为空
        // 则直接将 pre.left 指向 cur.left
        else if (cur.left != null) {
          pre.left = cur.left;
        }
        
        // 当前节点的左右子节点均为空，则直接删除，pre.left 指向空
        else {
          pre.left = null;
        }
      }
		
      // 父节点的值小于当前节点的值，说明需要删除的点是右子节点
      if (pre.val < key) {
        if (cur.right != null && cur.left != null) {
          pre.right = cur.left;
          TreeNode node = cur.left;
          while (node.right != null) {
            node = node.right;
          }
          node.right = cur.right;
        }

        else if (cur.right != null) {
          pre.right = cur.right;
        }

        else if (cur.left != null) {
          pre.right = cur.left;
        }

        else {
          pre.right = null;
        }
      }

      break;
    }
  }

  return virtualHead.left;
}

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

题目描述

给你一个整数数组 nums，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。

高度平衡 二叉树是一棵满足 每个节点的左右两个子树的高度差不超过1 的二叉树。

建立模型

1. 每次去数组的中间值作为根节点
2. 使用左边界到中间值的子数组递归构建左子树
3. 使用中间值到右边界的子数组递归的构建右子树

代码实现

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

public TreeNode sortedArrayToBSTImpl(int[] nums, int left, int right) {
  if (left > right) {
    return null;
  }

  int mid = left + (right - left) / 2;
  TreeNode node = new TreeNode(nums[mid]);
  node.left = sortedArrayToBSTImpl(nums, left, mid - 1);
  node.right = sortedArrayToBSTImpl(nums, mid + 1, right);

  return node;
}