exact O(h) time


  • 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 {
        // two cases
        // (1) right tree is null, just let leftsubtree replace current node
        // (2) right tree is not null, 
        // find right tree leftmost node, put current node left tree to this node left tree
        // use current node right tree replace current node
        TreeNode preNode = null;
        public TreeNode deleteNode(TreeNode root, int key) {
            TreeNode node = findNode(root, key);
            if (node == null) return root;
            
            // node.right == null case
            if (node.right == null) {
                if (preNode == null) return node.left;
                if (preNode.val < key) {
                    preNode.right = node.left;
                } else {
                    preNode.left = node.left;
                }
                return root;
            }
            
            // node has right
            TreeNode tmp = node.right;
            while (tmp.left != null) tmp = tmp.left;
            tmp.left = node.left;
            if (preNode == null) return node.right;
            if (preNode.val < key) {
                preNode.right = node.right;
            } else {
                preNode.left = node.right;
            }
            return root;
        }
        private TreeNode findNode(TreeNode root, int key) {
            if (root == null) return null;
            if (root.val == key) return root;
            if (root.val < key) {
                preNode = root;
                return findNode(root.right, key);
            }
            preNode = root;
            return findNode(root.left, key);
        }
    }

Log in to reply
 

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