Java Solution - manipulate by reference rather than by value


  • 0
    M

    If interviewer does not allow us to alter the values of nodes, we would need to manipulate the nodes by reference. Here's the solution in this case.

            public TreeNode deleteNode(TreeNode root, int key) {
                if (root == null) return null;
    		TreeNode pRoot = new TreeNode(0);
    		pRoot.left = root;
    		TreeNode p = pRoot, cur = root;
    		while (cur != null && cur.val != key) {
    			p = cur;
    			if (key < cur.val) {
    				cur = cur.left;
    			} else {
    				cur = cur.right;
    			}
    		}
    		if (cur == null) return root;
    		delete(cur, p);
    		return 	pRoot.left;
            }
    	private TreeNode delete(TreeNode node, TreeNode p) {
    		if (node == null) return null;
    		boolean isLeft = p.left == node;
    		if (node.left == null) {
    			if (isLeft) p.left = node.right;
    			else p.right = node.right;
    			return node.right;
    		}
    		if (node.right == null) {
    			if (isLeft) p.left = node.left;
    			else p.right = node.left;
    			return node.left;
    		}		
    		TreeNode left = node.left, right = node.right;
    		TreeNode p1 = node, left1 = left;
    		while (left1.right != null) {
    			p1 = left1;
    			left1 = left1.right;
    		}
    		TreeNode newLeft = delete(left1, p1);
    		if (left1 == left) left = newLeft;
    		left1.left = left;
    		left1.right = right;
    		if (isLeft) p.left = left1;
    		else p.right = left1;
    		return left1;
    	}
    

Log in to reply
 

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