Delete Node in a BST-K6K4.com

原题： https://leetcode.com/problems/delete-node-in-a-bst/description/

题意： 给定一个BST的根节点与一个key，删除BST中key对应的节点。返回BST根节点的引用（有可能被更新）。基本上，删除操作分为两个阶段：（1）寻找待删除节点（2）如果节点找到，删掉这个节点

约定： 时间复杂度为O(树的高度)

例子：

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

给定删除 key对应的节点是3。所以我们找到值为3的节点并删除它。

一个有效的答案是 [5,4,6,2,null,null,7], 在下面的BTS中展示出来。

    5
   / \
  4   6
 /     \
2       7

另一个有效的答案是 [5,2,6,null,4,null,7]。

    5
   / \
  2   6
   \   \
    4   7

标签： bst、null、删除、节点、bts、面试

猜你感兴趣的圈子：

LeetCode交流圈

星空

2017-08-18 17:18:20 1楼#1层

class Solution(object):
    def deleteNode(self, root, key):
        """
        :type root: TreeNode
        :type key: int
        :rtype: TreeNode
        """
        pre, cur = None, root
        while cur and cur.val != key:
            pre = cur
            if key < cur.val:
                cur = cur.left
            elif key > cur.val:
                cur = cur.right
        if not cur: return root

        ncur = cur.right
        if cur.left:
            ncur = cur.left
            self.maxChild(cur.left).right = cur.right

        if not pre: return ncur

        if pre.left == cur:
            pre.left = ncur
        else:
            pre.right = ncur
        return root

    def maxChild(self, root):
        while root.right:
            root = root.right
        return root

星空

2017-08-18 17:18:42 2楼#1层

public class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null){
            return null;
        }
        if(key < root.val){
            root.left = deleteNode(root.left, key);
        }else if(key > root.val){
            root.right = deleteNode(root.right, key);
        }else{
            if(root.left == null){
                return root.right;
            }else if(root.right == null){
                return root.left;
            }
            root.val = findMax(root.left).val;
            root.left = deleteNode(root.left, root.val);
        }
        return root;
    }
    
    private TreeNode findMax(TreeNode node){
        while(node.right != null){
            node = node.right;
        }
        return node;
    }
}

星空

2017-08-18 17:19:59 3楼#1层

class Solution {
    private TreeNode deleteRootNode(TreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.left == null) {
            return root.right;
        }
        if (root.right == null) {
            return root.left;
        }
        TreeNode next = root.right;
        TreeNode pre = null;
        for(; next.left != null; pre = next, next = next.left);
        next.left = root.left;
        if(root.right != next) {
            pre.left = next.right;
            next.right = root.right;
        }
        return next;
    }
    
    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode cur = root;
        TreeNode pre = null;
        while(cur != null && cur.val != key) {
            pre = cur;
            if (key < cur.val) {
                cur = cur.left;
            } else if (key > cur.val) {
                cur = cur.right;
            }
        }
        if (pre == null) {
            return deleteRootNode(cur);
        }
        if (pre.left == cur) {
            pre.left = deleteRootNode(cur);
        } else {
            pre.right = deleteRootNode(cur);
        }
        return root;
    }
}

星空

2017-08-18 17:20:59 4楼#1层

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) return nullptr;
        if (root->val == key) {
            if (!root->right) {
                TreeNode* left = root->left;
                delete root;
                return left;
            }
            else {
                TreeNode* right = root->right;
                while (right->left)
                    right = right->left;
                swap(root->val, right->val);    
            }
        }
        root->left = deleteNode(root->left, key);
        root->right = deleteNode(root->right, key);
        return root;
    }
};

取消

回复

推荐圈子

LeetCode交流圈