LC.450 ｜ 删除二叉搜索树中的节点 ｜ 树 ｜ 暴力重构/转化思维

输入：
二叉搜索树的根节点root和一个需要删除的值key。

要求：
删除 BST 中的指定节点，并保证二叉搜索树性质不变。

输出：
删除后的新树根节点。

思路：

这道题的标准解法通常涉及复杂的指针操作（特别是处理双子节点的情况）。但在实际解题或笔试中，如果我们一时无法理清复杂的指针断连逻辑，可以转换思维，利用“数据结构的特性”来降维打击。
当然这题自然有正规写法，等回头思路清晰了再来写，今天先来个暴力写法开开胃。
本题解采用“暴力重构”策略：
既然在树上直接修补很难，不如利用 BST 的性质：

1. 拆迁（遍历）：二叉搜索树本质上就是一堆有序的数据。我们可以先遍历整棵树，把除了目标key以外的所有节点值都收集到一个数组中。
2. 重建（构造）：拿着这个干净的数组，直接调用“构建二叉搜索树”（参考 LC.1008）的逻辑，重新盖一棵新树。

虽然这种方法在空间和时间上不是最优（涉及大量内存分配），但它逻辑极其简单，不易出错，是一种非常实用的“工程化”解题思路——解决不了问题，就解决提出问题的人（节点），然后重新组队。

复杂度：

• 时间复杂度：O(N)O(N)O(N)
  • 遍历收集节点需要O(N)O(N)O(N)，重新构建树也需要O(N)O(N)O(N)。虽然常数项较大，但量级依然是线性的。
• 空间复杂度：O(N)O(N)O(N)
  • 需要一个数组来存储所有节点的值，加上递归栈的空间。

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode():val(0),left(nullptr),right(nullptr){}TreeNode(intx):val(x),left(nullptr),right(nullptr){}TreeNode(intx,TreeNode*left,TreeNode*right):val(x),left(left),right(right){}};classSolution{public:TreeNode*deleteNode(TreeNode*root,intkey){vector<int>vals;preorder(root,vals,key);returnbuildTree(vals);}voidpreorder(TreeNode*root,vector<int>&vals,intkey){if(!root)return;if(root->val!=key){vals.push_back(root->val);}preorder(root->left,vals,key);preorder(root->right,vals,key);}// 照搬 LC.1008 的逻辑TreeNode*buildTree(vector<int>&pre){if(pre.size()==0)returnnullptr;TreeNode*root=newTreeNode(pre[0]);vector<int>leftPart,rightPart;for(inti=1;i<pre.size();i++){if(pre[i]<pre[0])leftPart.push_back(pre[i]);elserightPart.push_back(pre[i]);}root->left=buildTree(leftPart);root->right=buildTree(rightPart);returnroot;}};