本文主要是介绍代码随想录——删除二叉搜索树中的节点(Leetcode450),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接
递归
/*** 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) {// 如果当前的节点是空的,那么二叉搜索树也是空的,因此返回null。if(root == null){return null;}// 如果当前节点的值大于要删除的键值(key),递归地在左子树中删除键值。if(root.val > key){root.left = deleteNode(root.left,key);return root;}// 如果当前节点的值小于要删除的键值,递归地在右子树中删除键值。if(root.val < key){root.right = deleteNode(root.right,key);return root;}// 如果找到了要删除的键值,这里有几种情况需要处理if(root.val == key){// 如果该节点没有子节点,可以直接删除该节点if(root.left == null && root.right == null){return null;}// 如果该节点只有右子节点,可以将根节点替换为它的右子节点if(root.right == null){return root.left;}// 如果该节点只有左子节点,可以将根节点替换为它的左子节点if(root.left == null){return root.right;}// 如果该节点既有左子节点又有右子节点,需要找到右子树中的最小值(或最大值,因为BST的右子树只包含大于当前节点的值)节点,将其移动到当前节点的位置,然后删除那个最小值(或最大值)节点在右子树中的位置。TreeNode successor = root.right;// 为此,需要找到这个最小值(或最大值)节点的左子节点,并将它复制到当前节点的右子节点,然后删除这个最小值(或最大值)节点。这个步骤通过递归地在右子树中查找最小值节点来实现。在找到这个节点后,需要将这个节点的右子树连接到当前节点原来的右子节点上,同时将这个最小值(或最大值)节点的左子树连接到当前节点上。while(successor.left != null){successor = successor.left;}root.right = deleteNode(root.right,successor.val);successor.right = root.right;successor.left = root.left;return successor;}return root;}
}
注意多种情况考虑
这篇关于代码随想录——删除二叉搜索树中的节点(Leetcode450)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!