[leetcode] 450. Delete Node in a BST

[leetcode] 450. Delete Node in a BST

Description

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:

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 7Given 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 7Another valid answer is [5,2,6,null,4,null,7]. 5 / \ 2 6 \ \ 4 7

分析

题目的意思是：删除二叉搜索树中的指定结点。

首先判断根节点是否为空。由于BST的左<根<右的性质，使得我们可以快速定位到要删除的节点，我们对于当前节点值不等于key的情况，根据大小关系对其左右子节点分别调用递归函数。若当前节点就是要删除的节点，我们首先判断是否有一个子节点不存在，那么我们就将root指向另一个节点，如果左右子节点都不存在，那么root就赋值为空了，也正确.难点就在于处理左右子节点都存在的情况，我们需要在右子树找到最小值，即右子树中最左下方的节点，然后将该最小值赋值给root，然后再在右子树中调用递归函数来删除这个值最小的节点.

代码

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

参考文献

​​[LeetCode] Delete Node in a BST 删除二叉搜索树中的节点​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。