频道栏目
首页 > 考试 > 其他 > 正文

Delete Node in a BST

2018-01-25 12:01:10         来源:dongyu_1989的博客  
收藏   我要投稿

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

  1. Search for a node to remove.If the node is found, delete the node.

     

    Note:Time complexity should be O(height of tree).

    Example:

    root = [5,3,6,2,4,null,7]
    key = 3
    
        5
       / \
      3   6
     / \   \
    2   4   7
    
    Given key to delete is 3. So we find the node with value 3 and delete it.
    
    One valid answer is [5,4,6,2,null,null,7], shown in the following BST.
    
        5
       / \
      4   6
     /     \
    2       7
    
    Another valid answer is [5,2,6,null,4,null,7].
    
        5
       / \
      2   6
       \   \
        4   7
    
    
    /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { if(!root) return NULL; if(root->val>key) { root->left = deleteNode(root->left, key); }else if(root->valright = deleteNode(root->right, key); }else { if(!root->left || !root->right) { root = (root->left) ? root->left : root->right; }else { TreeNode * cur = root->right; while(cur->left) { cur = cur->left; } root->val = cur->val; root->right = deleteNode(root->right, cur->val); } } return root; } };


    非递归:
    class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { TreeNode *cur = root, *pre = NULL; while (cur) { if (cur->val == key) break; pre = cur; if (cur->val > key) cur = cur->left; else cur = cur->right; } if (!cur) return root; if (!pre) return del(cur); if (pre->left && pre->left->val == key) pre->left = del(cur); else pre->right = del(cur); return root; } TreeNode* del(TreeNode* node) { if (!node->left && !node->right) return NULL; if (!node->left || !node->right) { return (node->left) ? node->left : node->right; } TreeNode *pre = node, *cur = node->right; while (cur->left) { pre = cur; cur = cur->left; } node->val = cur->val; (pre == node ? node->right : pre->left) = cur->right; return node; } };
上一篇:Jolly Jumpers【序列】解析
下一篇:编程开发上升序列问题解析
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站