代码随想录算法训练营第22天|235.二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点

一、力扣235.二叉搜索树的最近公共祖先

1.1 题目

1.2 思路

利用二叉搜索树的有序特性来实现：
如果cur大于pq：向左搜索；
如果cur小于pq：向右搜索；
如果介于两者之间：则找到！

1.3 代码

递归法：

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//递归法if(root == null){return null;}return traversal(root,p,q);}public TreeNode traversal(TreeNode root,TreeNode p,TreeNode q){//和上题类似，第二种情况也包含在了处理逻辑里if(root.val < p.val && root.val < q.val){return traversal(root.right,p,q);}if(root.val > p.val && root.val > q.val){return traversal(root.left,p,q);}//当前节点介于[p,q]  闭区间return root;}
}

迭代法：

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//迭代if(root == null){return null;}TreeNode cur = root;while(true){if(cur.val > p.val && cur.val > q.val){cur = cur.left;continue;}if(cur.val < p.val && cur.val < q.val){cur = cur.right;continue;}return cur;}}
}

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

2.1 题目

2.2 思路

根据二叉搜索树的特性，比大小向下遍历，直到找到null，将其new一个新的结点插入进去。

2.3 代码

自己的思路：

class Solution {public TreeNode newnode;public TreeNode insertIntoBST(TreeNode root, int val) {//比大小来遍历寻找该插入的位置if(root == null){return new TreeNode(val);}traversal(root,val);return root;}public void traversal(TreeNode root,int val){if(val > root.val){if(root.right == null){newnode = new TreeNode(val);root.right = newnode;return;}traversal(root.right,val);}if(val < root.val){if(root.left == null){newnode = new TreeNode(val);root.left = newnode;return;}traversal(root.left,val);}}
}

三、力扣450.删除二叉搜索树中的节点

3.1 题目

3.2 思路

梳理本题的五种情况：
（1）没有找到该节点
（2）找到了该节点，该节点的左右孩子均为空
（3）找到了该节点，该节点的左孩子为空，右孩子不为空
（4）找到了该节点，该节点的左孩子不为空，右孩子为空
（5）找到了该节点，该节点的左右孩子均不为空（最关机键的点）：见下图

3.3 代码

class Solution {public TreeNode deleteNode(TreeNode root, int key) {//确定递归的终止条件//没有找到该节点if(root == null){return null;}//找到了该节点if(root.val == key){if(root.left == null && root.right == null){return null;}else if(root.left != null && root.right == null){return root.left;}else if(root.left == null && root.right != null){return root.right;}else{//假设root的右子树上位,那么需要将root的左子树插入root的右子树中，再返回右子树TreeNode cur = root.right;while(cur.left != null){cur = cur.left;}cur.left = root.left;return root.right;}}//单层递归逻辑if(key > root.val){root.right = deleteNode(root.right,key);}if(key < root.val){root.left = deleteNode(root.left,key);}return root;}
}

3.4 总结

（1）五种情况的分析；（递归终止条件）
（2）不用双指针pre，而是将处理后的结点回溯返回给上层节点接住。（单层递归逻辑）