题目大意

将一颗二叉搜索树，改为只有右子节点的二叉搜索树。

解题思路

  • 遍历一遍，存储节点值，按照题意重建二叉搜索树。空间开销大
  • 原地改变。

要点：

  1. 怎样找到重建后的BST的root。
  2. pre节点的传递，形参or返回值or全局变量

坑点：
要把左子节点都置为空，我说怎么一直报错，无限递归。最后一个节点也要置空..

Code

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     TreeNode* pre = nullptr;
  15.     TreeNode* ans = nullptr;
  16.     void dfs(TreeNode* cur) {
  17.         if (cur == nullptr) return ;
  19.         dfs(cur->left);
  20.         if (pre != nullptr) {
  21.             pre->left = nullptr;
  22.             pre->right = cur;
  23.         }
  24.         pre = cur;
  25.         if (ans == nullptr || (ans->val > cur->val)) ans = cur;  
  26.         dfs(cur->right);
  27.     }
  28.     TreeNode* increasingBST(TreeNode* root) {
  29.         dfs(root);
  30.         pre->left = pre->right = nullptr;
  31.         return ans;
  32.     }
  33. };
  36. /**
  37.     精简版 因为是中序遍历，第一次遍历到中的就是new_root，
  38.     2. 同样因为是中序遍历，所以遍历到中时左子节点已经无用了
  39.     所以直接把cur->left==nullptr即可。
  40.  */
  41. class Solution {
  42. public:
  43.     TreeNode* pre = nullptr;
  44.     TreeNode* ans = nullptr;
  45.     void dfs(TreeNode* cur) {
  46.         if (cur == nullptr) return ;
  48.         dfs(cur->left);
  50.         if (ans == nullptr) ans = cur;  
  51.         if (pre != nullptr) pre->right = cur; 
  52.         cur->left = nullptr;
  53.         pre = cur;
  55.         dfs(cur->right);
  56.     }
  57.     TreeNode* increasingBST(TreeNode* root) {
  58.         dfs(root);
  59.         return ans;
  60.     }
  61. };