Non-recursive Java Algorithm, 7ms


  • 0
    F
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public TreeNode deleteNode(TreeNode root, int key) {
            TreeNode cur = root, pre = null;
            
            while(cur!=null && cur.val!=key) {
                if(cur.val < key) {
                    pre = cur;
                    cur = cur.right;
                } else {  // cur.val > key
                    pre = cur;
                    cur = cur.left;
                }
            }
            
            if(cur == null) {
                return root;
            } else if(cur.right == null) {
                if(pre == null) {
                    return cur.left;
                } else {
                    if(pre.left == cur) {
                        pre.left = cur.left;
                    } else {
                        pre.right = cur.left;
                    }
                    return root;
                }
            } else {
                TreeNode cur1 = cur.right, pre1 = null;
                
                while(cur1!=null && cur1.left!=null) {
                    pre1 = cur1;
                    cur1 = cur1.left;
                }
                
                if(pre1 != null) {
                    pre1.left = cur1.right;
                    cur1.right = cur.right;
                }
                cur1.left = cur.left;
                if(pre == null) {
                    return cur1;
                } else {
                    if(pre.left == cur) {
                        pre.left = cur1;
                    } else {
                        pre.right = cur1;
                    }
                    return root;
                }
            }
        }
    }
    

Log in to reply
 

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