删除二叉搜索树中的节点
1、二叉搜索树的三个特性:
这些性质最好在面试之前了解清楚:
- 1、二叉搜索树的中序遍历的序列是递增排序的序列。中序遍历的遍历次序:
Left -> Node -> Right
。
public LinkedList<Integer> inorder(TreeNode root, LinkedList<Integer> arr) { if (root == null) return arr; inorder(root.left, arr); arr.add(root.val); inorder(root.right, arr); return arr; }
2、Successor
代表的是中序遍历序列的下一个节点。即:比当前节点大的最小节点,简称后继节点。
算法:先取当前节点的right节点(如果等于null ?),然后一直取该节点的left节点,直到left节点为空,则最后指向的节点为后继节点。
public int successor(TreeNode root) { root = root.right; while (root.left != null) root = root.left; return root; }
3、Predecessor
代表的是中序遍历序列的前一个节点。即:比当前节点小的最大节点,简称前驱节点。
算法:先取当前节点的left节点(等于null ?),然后取该节点的right节点,直到right节点为空,则最后指向的节点为前驱节点。
public int predecessor(TreeNode root) { root = root.left; while (root.right != null) root = root.right; return root; }
2、方法:递归
这里有三种可能的情况:
- 1、要删除的节点为叶子节点(没有子节点),可以直接删除。
- 2、要删除的节点不是叶子节点且拥有右节点,则该节点可以由该节点的后继节点进行替代,该后继节点位于右子树中较低的位置。然后可以从后继节点的位置递归向下操作以删除后继节点。
- 要删除的节点不是叶子节点,且没有右节点但是有左节点。这意味着它的后继节点在它的上面,但是我们并不想返回。我们可以使用它的前驱节点进行替代,然后再递归的向下删除前驱节点。
算法:
- 如果
key > root.val
,说明要删除的节点在右子树,root.right = deleteNode(root.right, key)
。 - 如果
key < root.val
,说明要删除的节点在左子树,root.left = deleteNode(root.left, key)
。 - 如果
key == root.val
,则该节点就是我们要删除的节点,则:- 如果该节点是叶子节点,则直接删除它:
root = null
。 - 如果该节点不是叶子节点且有右节点,则用它的后继节点的值替代
root.val = successor.val
,然后删除后继节点。 - 如果该节点不是叶子节点且只有左节点,则用它的前驱节点的值替代
root.val = predecessor.val
,然后删除前驱节点。
- 如果该节点是叶子节点,则直接删除它:
- 返回
root
。
class Solution { /* One step right and then always left */ public int successor(TreeNode root) { root = root.right; while (root.left != null) root = root.left; return root.val; } /* One step left and then always right */ public int predecessor(TreeNode root) { root = root.left; while (root.right != null) root = root.right; return root.val; } public TreeNode deleteNode(TreeNode root, int key) { if (root == null) return null; // delete from the right subtree if (key > root.val) root.right = deleteNode(root.right, key); // delete from the left subtree else if (key < root.val) root.left = deleteNode(root.left, key); // delete the current node else { // the node is a leaf if (root.left == null && root.right == null) root = null; // the node is not a leaf and has a right child else if (root.right != null) { root.val = successor(root); root.right = deleteNode(root.right, root.val); } // the node is not a leaf, has no right child, and has a left child else { root.val = predecessor(root); root.left = deleteNode(root.left, root.val); } } return root; } }
复杂度分析:
- 时间复杂度:O(logN)。在算法的执行过程中,我们一直在树上向左或向右移动。首先先用O(H1) 的时间找到要删除的节点,H1 值得是从根节点到要删除节点的高度。
- 然后删除节点需要O(H2) 的时间,H2 指的是从要删除节点到替换节点的高度。
- 由于O(H1+H2)=O(H),HH 值得是树的高度,若树是一个平衡树则 HH =logN。
- 空间复杂度:O(H),递归时堆栈使用的空间,HH 是树的高度。