题目链接
删除二叉搜索树中的节点
题目描述
注意点
- 节点值唯一
- root 是合法的二叉搜索树
- 节点数的范围 [0, 10000]
解答思路
- 可以根据二叉搜索树的性质找到要删除的节点,关键是删除节点后怎么重新构建成一棵新的二叉搜索树
- 首先要找到的是删除节点node的父节点node.parent,在删除node后,该节点树构建成一棵新的二叉搜索树,node.parent应该指向新的二叉搜索树的根节点
- 其次删除节点对应的节点树node怎么构成一棵新的二叉搜索树,应该将node.right作为新的二叉搜索树的根节点newRoot,newRoot的右子树就是原来的右子树不变;newRoot的左子树也是原来的左子树,在此基础上,newRoot的左子树左下角的节点(newRoot此时的最小值)的左子树还要连接上node.left,不然node的左子树就会丢失
- 需要注意的是,如果node的右子树为空,则直接将node的左子树作为新的二叉搜索树即可
代码
/*** 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) {// 方便分析删除根节点的情况TreeNode preRoot = new TreeNode(Integer.MAX_VALUE, root, null);// key的根节点TreeNode targetRoot = preRoot;// 找到key对应节点的根节点while (targetRoot != null) {// key大于当前节点,则key肯定在targetRoot右子树中if (targetRoot.val < key) {if (targetRoot.right == null) {break;}// 找到了要删除的节点->targetRoot.rightif (targetRoot.right.val == key) {targetRoot.right = reBuildTree(targetRoot.right);break;}targetRoot = targetRoot.right;}// key小于当前节点,则key肯定在targetRoot左子树中if (targetRoot.val > key) {if (targetRoot.left == null) {break;}// 找到了要删除的节点->targetRoot.leftif (targetRoot.left.val == key) {targetRoot.left = reBuildTree(targetRoot.left);break;}targetRoot = targetRoot.left;}}return preRoot.left;}/*** 重建树,删除root,root右子树根节点作为newRoot,newRoot右子树无变化,左子树左下角节点(最小值)连接root左子树根节点*/public TreeNode reBuildTree(TreeNode root) {// 无右子树,直接将左子树作为新的树if (root.right == null) {return root.left;}TreeNode newRoot = root.right;// 右子树左下角的节点连接左子树TreeNode rightMinNode = newRoot;while (rightMinNode.left != null) {rightMinNode = rightMinNode.left;}rightMinNode.left = root.left;return newRoot;}
}
关键点
- 删除某个节点怎么构建成新的二叉搜索树
- 注意边界问题(节点、子树为空的情况)