Java learned from CLRS


  • 0
    D
    public class Solution {
        private TreeNode root;
        private Map<TreeNode, TreeNode> parentMap = new HashMap<>();
        
        public TreeNode deleteNode(TreeNode root, int key) {
            if (root == null) {
                return null;
            }
            this.root = root;
            calculateParent(root, null, parentMap);
            TreeNode delNode = findNode(root, key);
            if (delNode == null) {
                return this.root;
            }
            TreeNode succNode = findSuccessor(delNode);
            if (delNode.left == null) {
                transplant(delNode, delNode.right, parentMap);
            } else if (delNode.right == null) {
                transplant(delNode, delNode.left, parentMap);
            } else {
                if (succNode != null && parentMap.get(succNode) != delNode) {
                    transplant(succNode, succNode.right, parentMap);
                    succNode.right = delNode.right;
                    parentMap.put(succNode.right, succNode);
                }
                transplant(delNode, succNode, parentMap);
                succNode.left = delNode.left;
                parentMap.put(delNode.left, delNode);
            }
            return this.root;
        }
        
        private void transplant(TreeNode u, TreeNode v, Map<TreeNode, TreeNode> parentMap) {
            if (parentMap.get(u) == null) {
                this.root = v;
            } else if (u == parentMap.get(u).left) {
                parentMap.get(u).left = v;
            } else {
                parentMap.get(u).right = v;
            }
            if (v != null) {
                parentMap.put(v, parentMap.get(u));
            }
        }
        
        private TreeNode findSuccessor(TreeNode node) {
            if (node == null) {
                return null;
            }
            TreeNode pNode = node.right;
            while (pNode != null && pNode.left != null) {
                pNode = pNode.left;
            }
            return pNode;
        }
        
        private TreeNode findNode(TreeNode root, int key) {
            if (root == null || root.val == key) {
                return root;
            }
            TreeNode ret = root.left == null ? null : findNode(root.left, key);
            return ret == null ? findNode(root.right, key) : ret;
        }
        
        private void calculateParent(TreeNode root, TreeNode parent, Map<TreeNode, TreeNode> parentMap) {
            if (root == null) {
                return;
            }
            parentMap.put(root, parent);
            calculateParent(root.left, root, parentMap);
            calculateParent(root.right, root, parentMap);
        }
    }
    

Log in to reply
 

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