https://docs.qq.com/doc/DUFBUQmxpQU1pa29C
669 我的思路，深度遍历每个节点。如果当前节点的值满足上下届区间继续递归遍历，如果不满足，进行处理逻辑，分情况讨论孩子节点的情况。
108
我的思路是中序构建二叉树，在调整为平衡树，因为之前没做中序构建二叉树的那道题，不知道原来不用调整为平衡树，由于分割的时候左右节点数相同，浑然天成的平衡二叉搜索树。
构造二叉树的核心思想是分治，不断中间分割，然后递归处理左右区间。
class Solution {
private:
TreeNode* traversal(vector<int>& nums, int left, int right){
if (left > right) return nullptr;
int mid = left + ((right - left) / 2);
TreeNode* root = new TreeNode(nums[mid]);
root->left = traversal(nums, left, mid - 1);
root->right = traversal(nums, mid + 1, right);
return root;
}
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
TreeNode* root = traversal(nums, 0, nums.size() - 1);
return root;
}
};
538
没思路，看了题解使用的双指针，但是怎么去更新cur呢，或许回溯？一开始怎么让cur指向最后一个节点呢，我想应该是递归遍历二叉搜索树，那要是普通树呢，二叉搜索树有什么特殊吗？想到二叉搜索树的特性，中序遍历有序递增，得到有序序列后，在累加，得到的序列根据中序重新构建二叉树？
简要概括就是反中序遍历，用双指针做累加
class Solution {
private:
int pre;
void traversal(TreeNode* cur){
if (cur == NULL) return;
traversal(cur->right);
cur->val += pre;
pre = cur->val;
traversal(cur->left);
}
public:
TreeNode* convertBST(TreeNode* root) {
pre = 0;
traversal(root);
return root;
}
};
总结：掌握如何利用递归函数的返回值增删二叉树
