Naive iterative java solution, find the node and make decision based on different situations


  • 0
    C

    '''
    public class Solution {

    public TreeNode deleteNode(TreeNode root, int key) {
        boolean isLeft = false;
        TreeNode node = root;
        TreeNode parent = null;
        while (node != null) {
            if (node.val > key) {
                parent = node;
                node = node.left;
                isLeft = true;
            } else if (node.val < key) {
                parent = node;
                node = node.right;
                isLeft = false;
            } else {
                break;
            }
        }
        if (node == null || node.val != key) {
            return root;
        }
        if (node.left == null && node.right == null) {
            if (node == root) {
                root = null;
            } else if (isLeft) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        } else if (node.left == null) {
            if (node == root) {
                root = root.right;
            } else if (isLeft) {
                parent.left = node.right;
            } else {
                parent.right = node.right;
            }
        } else if (node.right == null) {
            if (node == root) {
                root = root.left;
            } else if (isLeft) {
                parent.left = node.left;
            } else {
                parent.right = node.left;
            }
        } else {
            TreeNode successor = getSuccessor(node);
            if (node == root) {
                root = successor;
            } else if (isLeft) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            successor.left = node.left;
        }
        return root;
    }
    
    private TreeNode getSuccessor(TreeNode node) {
        TreeNode successor = null;
        TreeNode parent = null;
        TreeNode current = node.right;
        while (current != null) {
            parent = successor;
            successor = current;
            current = current.left;
        }
        if (successor != node.right) {
            parent.left = successor.right;
            successor.right = node.right;
        }
        return successor;
    }
    

    }
    '''


Log in to reply
 

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