中英文外贸网站建设,网站的领券商城怎么做,班级网站 建设模板,代做财务报表分析网站算法#xff1a;
一共有五种可能的情况#xff1a;
第一种情况#xff1a;没找到删除的节点#xff0c;遍历到空节点直接返回了找到删除的节点 第二种情况#xff1a;左右孩子都为空#xff08;叶子节点#xff09;#xff0c;直接删除节点#xff0c; 返回NULL为根…
算法
一共有五种可能的情况
第一种情况没找到删除的节点遍历到空节点直接返回了找到删除的节点 第二种情况左右孩子都为空叶子节点直接删除节点 返回NULL为根节点第三种情况删除节点的左孩子为空右孩子不为空删除节点右孩子补位返回右孩子为根节点第四种情况删除节点的右孩子为空左孩子不为空删除节点左孩子补位返回左孩子为根节点第五种情况左右孩子节点都不为空则将删除节点的左子树头结点左孩子放到删除节点的右子树的最左面节点的左孩子上返回删除节点右孩子为新的根节点。
第五种情况比如要删除节点7可以让它的左孩子或者右孩子去继位。这里是让左孩子去继位左孩子比7小右孩子比7大那左孩子应该继位在右孩子的最小的节点的左边即8左边。然后让3指向9。 调试过程
/*** 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;
//1.找不到key节点自动返回原rootif (root.val key) {
//2.左右都空,说明是叶子直接删除if (root.leftnull root.rightnull) return null;
//3.左空右不空右上移if (root.leftnull root.right!null) {root root.right;return root;}
//4.右空左不空左上移 if (root.left!null root.rightnull) {root root.left;return root;}
//5.左右都不空root的左孩子移到右孩子的最左边if (root.left!null root.right!null){TreeNode left root.left;root root.right;while (root.left!null){root root.left;}root.left left;return root;}}if (root.val key) deleteNode(root.left, key); if (root.val key) deleteNode(root.right, key); return root;}
} 原因
左右都不空时代码有问题。
代码逻辑不对没有中间变量cur相当于少了个变量cur去实现交换操作。
而且递归处没有赋值给root.left和root.right因为这里的递归是有返回值TreeNode的无法真正实现递归这一点老是忘记
修改后
/*** 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;
//1.找不到key节点自动返回原rootif (root.val key) {
//2.左右都空,说明是叶子直接删除if (root.leftnull root.rightnull) return null;
//3.左空右不空右上移if (root.leftnull root.right!null) {root root.right;return root;}
//4.右空左不空左上移 if (root.left!null root.rightnull) {root root.left;return root;}
//5.左右都不空root的左孩子移到右孩子的最左边if (root.left!null root.right!null){TreeNode cur root.right;while (cur.left!null){cur cur.left;}cur.left root.left;root root.right;return root;}}if (root.val key) root.leftdeleteNode(root.left, key); if (root.val key) root.rightdeleteNode(root.right, key); return root;}
}
原因
递归处逻辑不对。
应该是key比root.val小时向左搜索
应该是key比root.val大时向右搜索
正确代码
/*** 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;
//1.找不到key节点自动返回原rootif (root.val key) {
//2.左右都空,说明是叶子直接删除if (root.leftnull root.rightnull) return null;
//3.左空右不空右上移if (root.leftnull root.right!null) {root root.right;return root;}
//4.右空左不空左上移 if (root.left!null root.rightnull) {root root.left;return root;}
//5.左右都不空root的左孩子移到右孩子的最左边if (root.left!null root.right!null){TreeNode cur root.right;while (cur.left!null){cur cur.left;}cur.left root.left;root root.right;return root;}}if (key root.val) root.leftdeleteNode(root.left, key); if (key root.val) root.rightdeleteNode(root.right, key); return root;}
}
时间空间复杂度
时间复杂度
O(n)其中 n为 root的节点个数。最差情况下寻找和删除 cur各需要遍历一次树。
空间复杂度
O(n)其中 n为 root的节点个数。递归的深度最深为 O(n)。
