双非本科准备秋招（21.1）—— 力扣二叉搜索树

本文主要是介绍双非本科准备秋招（21.1）—— 力扣二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

刚学的二叉搜索树，做做题目巩固一下二叉搜索树的基本操作。

1、700. 二叉搜索树中的搜索

二叉搜索树的任何一个节点，都会大于左子树任意节点的值，都会小于右子树任意节点的值

class Solution {public TreeNode searchBST(TreeNode root, int val) {if(root == null) return null;TreeNode t = root;while(t != null){if(t.val < val){t = t.right;}else if(val < t.val){t = t.left;}else{return t;}}return null;}
}

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

插入操作，需要记录一下待插入节点的parent，如果parent是null，说明没有根，那么新加入的节点就是根节点，否则按照大小决定插入parent的左还是右。

class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {TreeNode t = root;TreeNode parent = null;while(t != null){parent = t;if(val < t.val){t = t.left;}else if(t.val < val){t = t.right;}}TreeNode node = new TreeNode(val);if(parent == null){return node;}if(val < parent.val){parent.left = node;}else{parent.right = node;}return root;}
}

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

分四种情况：

只有左子树
只有右子树
叶子节点
有左右子树

如果只有左子树，那么只需要把它的左孩子给它的parent节点就好，右子树同理，叶子节点一样，相当于子树为null，直接给parent也行。

如果有左右子树，那么需要用它的后继节点来替换自己，这样才能保证二叉搜索树的性质，后继节点一定不会有左子树，但可能有右子树，所以还要根据是否有右子树来判断一下。

这里用递归实现

class Solution {    public TreeNode deleteNode(TreeNode root, int key) {if(root == null){return null;}if(key < root.val){root.left = deleteNode(root.left, key);return root;}if(root.val < key){root.right = deleteNode(root.right, key);return root;}//只有左孩子if(root.right == null){return root.left;}//只有右孩子if(root.left == null){return root.right;}//都有TreeNode s = root.right;while(s.left != null){s = s.left;}s.right = deleteNode(root.right, s.val);s.left = root.left;return s;}
}