树的练习7--------LCR 052.递增顺序搜索树

前言

今天这一题也是非常的憋屈，在递归上的运用可谓是得心应手，但是在一些小细节上却存在着致命的问题，现在来总结一下。

题目：点这里

解法：

/** * 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 { public: vector<int> ret; int num; void inOrder(TreeNode* root){ if(root){ inOrder(root->left); ret.push_back(root->val); inOrder(root->right); } } TreeNode* dfs(int num){ if(num==ret.size()){ return NULL; } TreeNode* root = new TreeNode(ret[num]); root->right = dfs(++num);//如果是num++，那代表num是先传入再递增，传入的num的值永不改变，如果是++num，则代表是先递增后传入，虽然每次传入的num都增值了，但是本层函数中的num也增加了,这就使得后续传参错位。 root->left = NULL; // root->val = ret[num]; return root; } TreeNode* increasingBST(TreeNode* root) { ret.clear(); num = 0; inOrder(root); return dfs(num); } };

这个题目的思路很清晰，就是先将二叉搜索树利用前序遍历存入到数组中，然后将数组中的值利用遍历生成一棵符合要求的树。

小问题出现在第二步上，由于这棵树需要利用数组，所以我将索引作为形参来传递，但是在每次传入的值这里出了问题，如果传入的是num++，代表先传入后增值，那么在递归过程中num就不会改变了，也就进入了无穷次的递归；但如果改成++num，则代表先递增后传入，这样的话虽然num的值发生了改变，但是每一层的num却都加了不该加的1，导致归的时候根节点的赋值出现了错位，所以也是不对的；

我选择的补救措施是在递的时候提前赋值，就是这一行语句：

TreeNode* root = new TreeNode(ret[num]);

配合++num就能完美解决问题。

反思

还有这里相比用形参来传值，更好的做法是利用引用，这样可以增强代码的简洁性和可读性