数据结构与算法--二叉搜索树节点删除-蒲公英云

数据结构与算法--二叉搜索树节点删除

二叉搜索树的节点删除代码

class Solution { 
    public TreeNode deleteNode(TreeNode root, int key) { 
        if (root == null) { 
            return null;
        }
        if (key < root.val) { 
            // 待删除节点在左子树中
            root.left = deleteNode(root.left, key);
            return root;
        } else if (key > root.val) { 
            // 待删除节点在右子树中
            root.right = deleteNode(root.right, key);
            return root;
        } else { 
            // key == root.val，root 为待删除节点
            if (root.left == null) { 
                // 返回右子树作为新的根
                return root.right;
            } else if (root.right == null) { 
                // 返回左子树作为新的根
                return root.left;
            } else { 
                // 左右子树都存在，返回后继节点（右子树最左叶子）作为新的根
                TreeNode successor = min(root.right);
                successor.right = deleteMin(root.right);
                successor.left = root.left;
                return successor;
            }
        }
    }
    private TreeNode min(TreeNode node) { 
        if (node.left == null) { 
            return node;
        }
        return min(node.left);
    }
    private TreeNode deleteMin(TreeNode node) { 
        if (node.left == null) { 
            return node.right;
        }
        node.left = deleteMin(node.left);
        return node;
    }
}