Share my clean java solution


  • 0
    C
    // 要删除的节点 分三种情况:
    // 1. 叶子节点(左右子树均空):置双亲节点的指向该节点的链为空
    // 2. 只有左子树或者右子树:置双亲节点的指向该节点的链指向当前节点的孩子节点
    // 3. 左右子树均不为空:找到该节点的直接前驱,用直接前驱的值替换当前节点,然后删除原前驱节点,前驱节点的值定为情况1或者情况2中的一种
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) return root;
        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 != null && root.right != null){//case 3:
        	root.val = findMin(root.right).val;
        	root.right = deleteNode(root.right, root.val);
        }
        else{// case 1, 2:
        	root = (root.left != null) ? root.left : root.right;
        }
        return root;
    }
    public TreeNode findMin(TreeNode root){
    	if(root == null) return null;
    	while(root.left != null){
    		root = root.left;
    	}
    	return root;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.