为什么不交换两个节点？

Question

我试图解决leetcode中的一个问题—从BST中删除节点。我们将获得BST的根节点和密钥；我们必须删除以该键为值的节点。我们可以假设所有树节点都有唯一的值。我们必须在此操作后返回根节点。（问题链接为：https://leetcode.com/problems/delete-node-in-a-bst/description/).

我编写了以下代码：

// Example program
#include <iostream>
#include <string>

using namespace std;

  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

TreeNode* findSmallest(TreeNode* root) {
        if(!root) return NULL;

        TreeNode* prev=root;
        while(root->left) {
            cout<<"Visiting: "<<root->val<<"\n";
            prev=root;
            root=root->left;
        }
        prev->left=NULL;

        cout<<"Returning: "<<root->val<<" and prev was: "<<prev->val<<"\n";
        return root;
    }

    TreeNode* deleteNode(TreeNode* root, int key) {
        if(!root) return NULL;

        if(root->val == key) {
            //This is the node to be deleted
            TreeNode* smallestOnRight = findSmallest(root->right);

            //the lines below do not actually change the root node - why?
            if(smallestOnRight) smallestOnRight->left=root->left;
            if(smallestOnRight) smallestOnRight->right=root->right;
            root=smallestOnRight;

            return root;
        }

        if(root->val>key)
            deleteNode(root->left, key);
        if(root->val<key)
            deleteNode(root->right, key);

        return root;
    }

int main()
{
    TreeNode* root = new TreeNode(8);
    root->left = new TreeNode(3);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(6);
    root->left->right->left = new TreeNode(4);
    root->left->right->right = new TreeNode(7);

    root->right = new TreeNode(10);
    root->right->right = new TreeNode(14);
    root->right->right->left = new TreeNode(13);

    deleteNode(root, 3);

}

我想知道为什么评论下面的行实际上并没有改变根节点。所以，如果原始树像（a），那么在这个过程之后，新树像（b），而它应该像（c）：

（a） ：图像（a）
（b）：图像（b）
（c）：图像（c）

所以，基本上只有node3应该替换为node4，但不幸的是这并没有发生。为什么会这样？

编辑：因此输入为：

[8,3,10,1,6， null，14， null， null，4,7,13， null]
3

（树按级别顺序遍历）。

编辑：这是cpp。sh链接：http://cpp.sh/9h2z

Answer 1

您没有保留应该修改为指向node4的node8。您需要保留正在删除的节点的父节点并修改其中的链接。