补-代码随想录第22天| ● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点

本文主要是介绍补-代码随想录第22天| ● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

● 235. 二叉搜索树的最近公共祖先

思路：

一：递归

代码：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root.val>p.val&&root.val>q.val)return lowestCommonAncestor(root.left,p,q);if(root.val<p.val&&root.val<q.val)return lowestCommonAncestor(root.right,p,q);return root;}
}

二：迭代-利用特性

代码：向左右分支去查找，找到则返回

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {while (true) {if (root.val > p.val && root.val > q.val) {root = root.left;} else if (root.val < p.val && root.val < q.val) {root = root.right;} else {break;}}return root;}
}

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

思路：

思路一：递归

代码：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if(root==null)return new TreeNode(val);if(val<root.val)root.left=insertIntoBST(root.left,val);if(val>root.val)root.right=insertIntoBST(root.right,val);return root;}
}

思路二：迭代

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if(root==null)return new TreeNode(val);TreeNode newRoot = root;TreeNode pre = root;while(root!=null){pre=root;//存父节点if(val<root.val){root=root.left;}else if(val>root.val){root=root.right;}}if (pre.val > val) {//添加新结点pre.left = new TreeNode(val);} else {pre.right = new TreeNode(val);}return newRoot;}
}

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

思路：递归

举例：

代码：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode deleteNode(TreeNode root, int key) {// 第一种情况：没找到删除的节点，遍历到空节点直接返回了if(root==null)return root;if(root.val==key){// 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点if(root.left==null&&root.right==null){// root=null;return null;}// 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点else if(root.left==null&&root.right!=null){// root=root.right;return root.right;}// 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点else if(root.left!=null&&root.right==null){// root=root.left;return root.left;} // 第五种情况：左右孩子节点都不为空，// 则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置// 并返回删除节点右孩子为新的根节点。else{TreeNode cur=root.right;while(cur.left!=null){// 把要删除的节点（root）左子树放在cur的左孩子的位置cur=cur.left;}cur.left=root.left;root=root.right;// 返回旧root的右孩子作为新rootreturn root;}}if (root.val > key)root.left=deleteNode(root.left,key);if (root.val < key)root.right=deleteNode(root.right,key);return root;}
}

这篇关于补-代码随想录第22天| ● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---