p119 二叉搜索树中删除节点(leetcode 450)

时间：2020-04-13 16:57:16 收藏：0 阅读：64

一：解题思路

Time:O(h),Space:O(h),h为树的高度

二：完整代码示例 (C++版和Java版)

C++:

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;
            if (root->right == NULL) return root->left;

            TreeNode* leftMax = root->left;
            while (leftMax->right != NULL) leftMax = leftMax->right;
            leftMax->right = root->right;
            root = root->left;
        }

        return root;
    }
};

Java:

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;
                   if(root.right==null) return root.left;
                   
                   TreeNode leftMax=root.left;
                   while(leftMax.right!=null) leftMax=leftMax.right;
                   leftMax.right=root.right;
                   root=root.left;
               }
               
               return root;
        }
    }

原文：https://www.cnblogs.com/repinkply/p/12692302.html