果洛营销网站建设服务,网站制作 商城,哈尔滨网站排名公司,wordpress logo怎么换450删除二叉搜索树节点
删除结点分为2种情况#xff1a;
1.结点的孩子只有一个或没有#xff0c;则直接用孩子或空替代
2.结点的孩子有两个#xff0c;用左孩子替代#xff0c;将左孩子的右孩子移到结点右子树的最左结点
解法一#xff1a;递归
class Solution {publ…450删除二叉搜索树节点
删除结点分为2种情况
1.结点的孩子只有一个或没有则直接用孩子或空替代
2.结点的孩子有两个用左孩子替代将左孩子的右孩子移到结点右子树的最左结点
解法一递归
class Solution {public TreeNode deleteNode(TreeNode root, int key) {if (rootnull){return root;}if (root.valkey){if (root.leftnull){return root.right;}else if (root.rightnull){return root.left;}else {TreeNode son root.left;if (son.right!null){TreeNode rightnode son.right;TreeNode temp root.right;while (temp.left!null){temp temp.left;}temp.left rightnode;}son.right root.right;return son;}}else if (root.valkey){root.left deleteNode(root.left, key);}else {root.right deleteNode(root.right, key);}return root;}
}
解法二迭代
class Solution {public TreeNode deleteNode(TreeNode root, int key) {if (rootnull){return root;}TreeNode father null;TreeNode node root;while(node!null){if (node.valkey){break;}else if (node.valkey){father node;node node.left;} else {father node;node node.right;}}if (nodenull){return root;}TreeNode son null;if (node.leftnull){son node.right;}else if (node.rightnull){son node.left;}else {son node.left;if (son.right!null){TreeNode rightnode son.right;TreeNode temp node.right;while (temp.left!null){temp temp.left;}temp.left rightnode;}son.right node.right;}if (father!null){if (father.valnode.val){father.right son;}else {father.left son;}}else {root son;}return root;}
}
669修剪二叉搜索树
递归:
如果结点在范围内则左孩子右孩子进入递归返回结点
如果结点小于范围则右孩子进入递归返回右孩子递归结果
如果结点大于范围则左孩子进入递归返回左孩子递归结果
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if (rootnull){return root;}if (root.vallowroot.valhigh){root.left trimBST(root.left, low, high);root.right trimBST(root.right, low, high);return root;}else if (root.vallow){return trimBST(root.right, low, high);}else {return trimBST(root.left, low, high);}}
}
108有序数组转换为二叉搜索树
使用递归找到中间值为此结点值再将数组分割两半进入递归得到左孩子和右孩子
class Solution {public TreeNode sortedArrayToBST(int[] nums) {if (nums.length0){return null;}if (nums.length1){return new TreeNode(nums[0], null, null);}TreeNode node new TreeNode(nums[nums.length/2], null, null);node.right sortedArrayToBST(Arrays.copyOfRange(nums, nums.length/21, nums.length));node.left sortedArrayToBST(Arrays.copyOfRange(nums, 0, nums.length/2));return node;}
}
收获
注意二叉搜索树的结点顺序
