C# - iterative


  • 0
        public TreeNode DeleteNode(TreeNode root, int key) 
        {
            TreeNode parent = null;
            TreeNode node = root;
    
            // find node and track parent
            while (node != null && node.val != key)
            {
                parent = node;
                node = key < node.val ? node.left : node.right;
            }
            
            // not found
            if (node == null) return root;
    
            // build replacement - left tree with right tree appended to it's rightmost leaf
            TreeNode replacement = Combine(node.left, node.right);        
            if (parent == null)
            {
                // no parent replacing root
                return replacement;
            }
            else
            {
                if (parent.left == node) parent.left = replacement;
                if (parent.right == node) parent.right = replacement;
                return root;
            }
        }
        
        public TreeNode Combine(TreeNode left, TreeNode right)
        {
            if (left == null && right == null) return null;
            if (left == null) return right;
            if (right == null) return left;
            
            TreeNode head = left;
            while (left.right != null) left = left.right;
            left.right = right;
            return head;
        }
    

Log in to reply
 

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