代码随想录算法训练营DAY20 | 二叉树 (8)

一、LeetCode 701 二叉搜索树中的插入操作

题目链接： 701.二叉搜索树中的插入操作https://leetcode.cn/problems/insert-into-a-binary-search-tree/description/

思路：见缝插针罢辽。

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;*     }* }*/

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

题目链接：450.删除二叉搜索树中的节点https://leetcode.cn/problems/delete-node-in-a-bst/description/

思路：

        删除节点后的五种情况：

        ①未找到，返回null

        ②被删除节点为叶子结点，直接删除，返回null

        ③被删除节点左孩子空右不空，返回右孩子

        ④被删除节点右孩子空左不空，返回左孩子

        ⑤被删除节点左右皆不空，将删除节点的左子树头结点 放到删除节点的右子树的 最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

        第五种情况详解↓

要删除元素7

将7的左孩子5移动到右孩子9的最左边孩子节点

7的右孩子取代7的位置

class Solution {public TreeNode deleteNode(TreeNode root, int key) {//最终未找到if(root == null){return root;}//找到节点if(root.val == key){//左右孩子节点分别为空的情况，隐含了被删除节点为叶子节点的情况if(root.left == null){return root.right;}else if(root.right == null){return root.left;}else{//左右孩子节点都不为空TreeNode cur = root.right;while(cur.left != null){cur = cur.left;}cur.left = root.left;return root.right;}}//未到叶子结点、继续寻找if(key < root.val){//在左子树中寻找and删除root.left = deleteNode(root.left,key);}if(key > root.val){//在右子树中寻找and删除root.right = deleteNode(root.right,key);}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;*     }* }*/

三、小结

        赶上进度了ovo，呼~