讨论/《二叉搜索树》 - 删除二叉搜索树中的节点/
《二叉搜索树》 - 删除二叉搜索树中的节点
共 4 个回复

golang实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func deleteNode(root *TreeNode, key int) *TreeNode {
	if root == nil { //没找到,返回nil
		return nil
	}
	if key < root.Val {
		root.Left = deleteNode(root.Left, key) //向左子树搜索
	} else if root.Val < key {
		root.Right = deleteNode(root.Right, key) //向右子树搜索
	} else {    //找到了需要删除的节点
		if root.Left == nil { //第一种情况,被删除节点只有右子树,直接返回左子树
			return root.Right
		}
		if root.Right == nil {//第二种情况,被删除节点只有左子树,直接返回右子树
			return root.Left
		}
        
        //第三种情况,左右子树都不为空,分两种方法选取
        //第一种方法:找出需要删除节点的右子树的最小节点
		// min := root.Right
		// for min.Left != nil {
		// 	min = min.Left
		// }
		// min.Left = root.Left
		// root = root.Right
        
        //第二种方法:找出需要删除节点的左子树最大节点
        max := root.Left
        for max.Right != nil{
            max = max.Right
        }
        max.Right = root.Right
        root = root.Left
	}
	return root
}

java

/**
 * 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) {
        return delete(root, key);
    }

    private TreeNode delete(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        int cmp = key - root.val;
        if (cmp < 0) {
            root.left = delete(root.left, key);
        } else if (cmp > 0) {
            root.right = delete(root.right, key);
        } else {
            if (root.right == null) {
                return root.left;
            } else if (root.left == null)  {
                return root.right;
            }
            TreeNode temp = root;
            root = min(root.right);
            
            root.right = deleteMin(temp.right);
            root.left = temp.left;
            return root;
        }

        return root;
    }

    private TreeNode deleteMin(TreeNode node) {
        if (node.left == null) {
            return node.right;
        }
        node.left = deleteMin(node.left);
        return node;
    }

    private TreeNode min(TreeNode root) {
        if (root.left == null) {
            return root;
        } 
        return min(root.left);
    }

}

Java

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null)return null;
        if(key<root.val){
            root.left = deleteNode(root.left,key);
        }else if(key>root.val){
            root.right = deleteNode(root.right,key);
        }else{//key==root.val
            if(root.left == null && root.right == null){
                root = null;
            }else if(root.right == null){
                root = root.left;
            }else{
                TreeNode curr = root.right;
                while(curr.left != null){
                    curr = curr.left;
                }
                root.val = curr.val;
                root.right = deleteNode(root.right, root.val);
            }
        }
        return root;
    }
}

哦嘶

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(!root) return nullptr;
        if(key < root->val) root->left = deleteNode(root->left, key);
        else if(key > root->val) root->right = deleteNode(root->right, key);
        else{
            if(!root->left) return root->right;
            if(!root->right) return root->left;
            TreeNode* node = root->right;
            while(node->left) node = node->left;
            node->left = root->left;
            root = root->right;
        }
        return root;
    }
};