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; } };