代碼隨想錄算法刷題訓練營day22：LeetCode(236)二叉樹的最近公共祖先、LeetCode(235) 二叉搜索樹的最近公共祖先、LeetCode(701)二叉搜索樹中的插入操作、LeetCode(450)刪除二叉搜索樹中的節點

LeetCode(236)二叉樹的最近公共祖先
題目

代碼

/*** 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) {//判斷終止----------采用后續遍歷方法----從下往上遍歷//1、根為空if(root==null){return null;}//2、判斷左右子樹的情況-----遞歸思想----返回null---即為沒有if(root.val==p.val||root.val==q.val){return root;//返回當前的pq值---------上面判斷的是返回值}//遞歸遍歷----左右根//左右子樹的處理邏輯----查看左右子樹是否出現pq值----左右子樹為空--的那種情況TreeNode leftTreeNode=lowestCommonAncestor(root.left, p, q);TreeNode rightTreeNode=lowestCommonAncestor(root.right, p, q);//處理根節點-----重點------下面是判斷的是有沒有if(leftTreeNode!=null&&rightTreeNode!=null){return root;//說明左右子樹均找到p或者q的值}else if(leftTreeNode==null&&rightTreeNode!=null){return rightTreeNode;//有確定的了就不會發生變化了}else if(leftTreeNode!=null&&rightTreeNode==null){return leftTreeNode;}else{return null;}}
}

LeetCode(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) {//判斷終止條件//終止條件1、若根節點為空的時候if(root==null){return root;}//終止條件2、若根節點為pq的某個值時----此時在遍歷的時候就已經進行測試了if(root.val==p.val||root.val==q.val){return root;}//遞歸遍歷//先左子樹遍歷---發現左子樹是否包含p或者q值TreeNode leftTreeNode=lowestCommonAncestor(root.left, p, q);//同樣遍歷右子樹TreeNode rightTreeNode=lowestCommonAncestor(root.right, p, q);//處理根節點if(leftTreeNode!=null&&rightTreeNode!=null){return root;}else if(leftTreeNode!=null&&rightTreeNode==null){return leftTreeNode;}else if(leftTreeNode==null&&rightTreeNode!=null){return rightTreeNode;}else{return null;//對應前面考慮到的左右子樹均為空的情況----靜心判斷}}}

LeetCode(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){//此時為構造新節點占的位置TreeNode newNode=new TreeNode(val);return newNode;//把新子樹創建出來，并返回回去}//進行判斷，判斷朝左右子樹遞歸的方向if(root.val>val){root.left=insertIntoBST(root.left, val);//將判斷后的值連上}if(root.val<val){root.right=insertIntoBST(root.right, val);//將判斷后的右邊的值返回回去---左右兩邊僅有一邊的值進行返回}//連接完成之后，將根節點的值進行返回return root;//重點----仔細理解}
}

LeetCode(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) {//考慮刪除節點情況-----一共分為五種情況/* * 1、沒有找到刪除節點* 2、刪除節點為葉子節點* 3、刪除節點有左子樹，沒有右子樹* 4、刪除節點有右子樹，沒有左子樹* 5、刪除節點既有左子樹又有右子樹*///遞歸算法+先序遍歷----先處理根節點在處理左子樹和右子樹//遞歸的終止條件if(root==null){return null;//正常的終止條件------同時也是找不到刪除節點的情況}//第二個終止條件----即找到要刪除的元素if(root.val==key){//判斷四種刪除節點的情況//1、是葉子節點if(root.left==null&&root.right==null){return null;//返回為空，后面連接對應左子樹或者右子樹}else if(root.left!=null&&root.right==null){return root.left;//2、刪除節點有左子樹，沒有右子樹}else if(root.left==null&&root.right!=null){return root.right;//3、刪除節點有右子樹。沒有左子樹}else{//最復雜的一種情況---刪除根節點的左右子樹均不為空TreeNode currentNode=root.right;//找到右子樹最左邊的節點while (currentNode.left!=null) {currentNode=currentNode.left;}//將根節點的左子樹拿出來currentNode.left=root.left;//此時又變成左空由不空的情況return root.right;}}//終止條件處理完了，現在開始處理單次遞歸的情況if(root.val>key){//向左邊遍歷root.left=deleteNode(root.left, key);//此時返回的值直接連接到當前的根節點上}if(root.val<key){//向右邊遍歷root.right=deleteNode(root.right, key);}return root;//最后將根節點返回//最后將根節點返回}}