leetcode 450. Delete Node in a BST 二叉搜索树BST删除结点 + 深度优先遍历DFS

深碍√TFBOYSˉ_ 2022-06-04 09:10 170阅读 0赞

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

题意很简单，就是考察二叉搜索树BST的结点删除，记住吧，这是十分经典的问题

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <cmath>
    
    using namespace std;
    
    
    /*
    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 == NULL)
                return root;
            else
            {
                if (root->val == key)
                {
                    if (root->right == NULL)
                    {
                        TreeNode* left = root->left;
                        delete root;
                        return left;
                    }
                    else
                    {
                        TreeNode* right = root->right;
                        while (right->left != NULL)
                            right = right->left;
                        swap(root->val,right->val);
                    }
                }
                root->left = deleteNode(root->left, key);
                root->right = deleteNode(root->right, key);
                return root;
            }
        }
    };