随想录刷题笔记 —二叉树篇10 450删除二叉搜索树节点 669修剪二叉搜索树 108有序数组转换为二叉搜索树

450删除二叉搜索树节点

删除结点分为2种情况：

1.结点的孩子只有一个或没有，则直接用孩子或空替代

2.结点的孩子有两个，用左孩子替代，将左孩子的右孩子移到结点右子树的最左结点

解法一：递归

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 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.val>key){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 (root==null){return root;}TreeNode father = null;TreeNode node = root;while(node!=null){if (node.val==key){break;}else if (node.val>key){father = node;node = node.left;} else {father = node;node = node.right;}}if (node==null){return root;}TreeNode son = null;if (node.left==null){son = node.right;}else if (node.right==null){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.val<node.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 (root==null){return root;}if (root.val>=low&&root.val<=high){root.left = trimBST(root.left, low, high);root.right = trimBST(root.right, low, high);return root;}else if (root.val<low){return trimBST(root.right, low, high);}else {return trimBST(root.left, low, high);}}
}

108有序数组转换为二叉搜索树

使用递归，找到中间值为此结点值，再将数组分割两半进入递归得到左孩子和右孩子

class Solution {public TreeNode sortedArrayToBST(int[] nums) {if (nums.length==0){return null;}if (nums.length==1){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/2+1, nums.length));node.left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, nums.length/2));return node;}
}

收获

注意二叉搜索树的结点顺序