/**
-
Definition for a binary tree node.
-
struct TreeNode {
-
int val;
-
TreeNode *left;
-
TreeNode *right;
-
TreeNode() : val(0), left(nullptr), right(nullptr) {}
-
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
-
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
-
};
*/
class Solution {pair< TreeNode * , TreeNode * > Gettarget( TreeNode * & root , int & key )
{
TreeNode * prev = nullptr ;
TreeNode * curr = root ;while ( curr != nullptr ) { prev = curr ; if( key == curr->val ) break ; else if ( key > curr->val ) curr = curr->right ; else curr = curr->left ; } return { prev , curr } ;
}
void insert( TreeNode * root , TreeNode * insertedNode )
{
TreeNode * prev = nullptr , * curr = root ;bool isRight = false ; while ( curr != nullptr ) { prev = curr ; if( insertedNode->val > curr->val ) { isRight = 1 ; curr = curr->right ; } else { isRight = 0 ; curr = curr->left ; } } if( isRight ) { prev->right = insertedNode ; } else { prev->left = insertedNode ; }
}
public:
TreeNode* deleteNode(TreeNode* root, int key)
{pair< TreeNode * , TreeNode * > P = Gettarget( root , key ) ; if( P.second == nullptr ) //key is not found , nothing to delete return root ; // else TreeNode * prev = P.first , * curr = P.second ; if( curr->left == nullptr && curr->right == nullptr ) // zero child { if( prev == nullptr ) // delete the root node { delete curr ; root = nullptr ; return root ; } else { if( prev->left == curr ) prev->left = nullptr ; else prev->right = nullptr ; delete curr ; curr = nullptr ; return root ; } } else if ( curr->left != nullptr && curr->right == nullptr ) // single child { if( prev == nullptr ) { TreeNode * ans = curr->left ; curr->left = nullptr ; delete curr ; curr = nullptr ; return ans ; } else { TreeNode * ans = curr->left ; curr->left = nullptr ; if( prev->left == curr ) prev->left = ans ; else prev->right = ans ; delete curr ; curr = nullptr ; return root ; } } else if ( curr->left == nullptr && curr->right != nullptr ) { if( prev == nullptr ) { TreeNode * ans = curr->right ; curr->left = nullptr ; delete curr ; curr = nullptr ; return ans ; } else { TreeNode * ans = curr->right ; curr->right = nullptr ; if( prev->left == curr ) prev->left = ans ; else prev->right = ans ; delete curr ; curr = nullptr ; return root ; } } else { if( prev == nullptr ) { TreeNode * left = curr->left , * right = curr->right ; insert( right , left ) ; curr->left = curr->right = nullptr ; delete curr ; curr = nullptr ; return right ; } else { TreeNode * left = curr->left , * right = curr->right ; insert( right , left ) ; curr ->left = curr->right = nullptr ; if( prev->left == curr ) prev->left = right ; else prev->right = right ; delete curr ; curr = nullptr ; return root ; } }
}
};
i was trying to know why the error is occuring ? i dont want the soln , i already knows that , you can respone the correct eddited part of the code , thanks
.
President G is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.