Delete Node in a BST
BST中删除节点, 经典算法: 先BST搜到节点, 然后: 1. 如果左子树是空, 返回右子树. 2. 如果右子树是空, 返回左子树. 3. 两个都不是空的, 找到右子树最左的节点, 赋值给root, 然后继续删除右子树root的当前值.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
public class Solution { public TreeNode deleteNode(TreeNode root, int key) { if(root == null) return root; if(root.val < key) root.right = deleteNode(root.right,key); else if(root.val > key) root.left = deleteNode(root.left, key); else{ if(root.left == null) return root.right; else if(root.right == null) return root.left; else{ TreeNode min = root.right; while(min.left != null) min = min.left; root.val = min.val; root.right = deleteNode(root.right, root.val); } } return root; } } |