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

素颜马尾好姑娘i 2022-09-04 15:54 167阅读 0赞

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

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;
        }
    }