Iterative Java Solution - Beats 80%


  • 0
    G
    public class Solution {
        public TreeNode deleteNode(TreeNode root, int key) {
            if (root == null) return root;
            TreeNode prev = null;
            TreeNode iter = root;
            if(root.val == key){ // special case of head
                return mergeLeft(root.left,root.right);
            }
            boolean isLeftChild = false;
            while(iter != null){
                if(iter.val == key) {
                    if (isLeftChild) {
                        prev.left = mergeLeft(iter.left,iter.right);
                    } else {
                        prev.right = mergeLeft(iter.left,iter.right);
                    }
                    return root;
                }
                prev = iter;
                if(iter.val > key){
                    iter = iter.left;
                    isLeftChild = true;
                } else {
                    iter = iter.right;
                    isLeftChild = false;
                }
            }
            return root;//not found case
        }
        
        public TreeNode mergeLeft(TreeNode leftNode, TreeNode rightNode){
            if(leftNode == null) return rightNode;
            if(rightNode == null) return leftNode;
            TreeNode iterator = rightNode;
            while(iterator.left!=null) {
                iterator = iterator.left;
            }
            iterator.left =leftNode;
            return rightNode;
        }
    }
    

Log in to reply
 

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