lintcode-87-删除二叉查找树的节点

87-删除二叉查找树的节点

给定一棵具有不同节点值的二叉查找树，删除树中与给定值相同的节点。如果树中没有相同值的节点，就不做任何处理。你应该保证处理之后的树仍是二叉查找树。

样例

给出如下二叉查找树：

删除节点3之后，你可以返回：

或者：

标签

二叉查找树 LintCode 版权所有

思路

若要删除一个BST的一个结点，需要考虑如下三种情况：

需要删除的节点下并没有其他子节点
需要删除的节点下有一个子节点（左或右）
需要删除的节点下有两个子节点（既左右节点都存在）

对这三种情况分别采取的措施是：

直接删除此结点
删除此结点，将此结点父节点连接到此结点左（右）子树
找出此结点右子树中的最小结点，用以代替要删除的结点，然后删除此最小结点

code

/**

 * Definition of TreeNode:

 * class TreeNode {

 * public:

 *     int val;

 *     TreeNode *left, *right;

 *     TreeNode(int val) {

 *         this->val = val;

 *         this->left = this->right = NULL;

 *     }

 * }

 */

class Solution {

public:

    /**

     * @param root: The root of the binary search tree.

     * @param value: Remove the node with given value.

     * @return: The root of the binary search tree after removal.

     */

    TreeNode* removeNode(TreeNode* root, int value) {

        // write your code here

        if(root == NULL) {

            return NULL;

        }

        if(root->val > value) {

            root->left = removeNode(root->left, value);

        }

        else if(root->val < value) {

            root->right = removeNode(root->right, value);

        }

        else {

            if (root->left == NULL || root->right == NULL) {

                root = (root->left != NULL) ? root->left : root->right;

            }

            else {

                TreeNode *cur = root->right;

                while (cur->left != NULL) {

                    cur = cur->left;

                }

                root->val = cur->val;

                root->right = removeNode(root->right, cur->val);

            }

        }

        return root;

    }

};

巴特西

lintcode-87-删除二叉查找树的节点

87-删除二叉查找树的节点

样例

标签

思路

code

最新文章

热门文章