第21天，二叉树最后一篇，冲💪
目录
669.修建二叉搜索树
108.将有序数组转换为二叉搜索树
538.把二叉搜索树转换为累加树
二叉树总结
669.修建二叉搜索树
文档讲解：代码随想录修建二叉搜索树
视频讲解：手撕修建二叉搜索树
题目：
学习：
本题需要注意的点很多，不能够轻易的就把节点删除，首先：1.本题给出的最小边界值和最大边界值，不一定会存在树中，只是提供一个区间大小，因此不能够节点判断是否等于low或者high。2.在找到小于low的值后不能够直接将其删除，因为它的右孩子不一定小于low，同理大于high的节点也不能直接删除，还需要关注它的左孩子。3.在2的基础上，也不能直接把右孩子返回，因为右孩子大于low的情况下，右孩子的左孩子还是可能会小于low需要删除，因此还需要不断的进行遍历。（该情况如下图所示，如果区间在[2,3]之间）
依据上述所说，来设计递归三部曲。
代码：
//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:
//确定返回值，本题需要重新构造二叉树节点，因此使用返回值更加方便，当然也可以没有返回值就需要手动进行左右孩子构造
TreeNode* trimBST(TreeNode* root, int low, int high) {
//确定终止条件
if (root == nullptr) return nullptr;
//确定单层递归逻辑（核心是将root转移到low和high区间内）
//1.当前值大于high
if (root->val > high) {
//在该节点左边找寻是否有合适的值
return trimBST(root->left, low, high);
}
//2.当前值小于low
if (root->val < low) {
//在该节点右边找寻是否有合适的值
return trimBST(root->right, low, high);
}
//3.当前值在low和high区间内，但是还不能就此下定义，还需要判断该节点左右孩子是否合格
root->left = trimBST(root->left, low, high);
root->right = trimBST(root->right, low, high);
//持续把修改后的节点返回上层
return root;
}
};代码：本题也能够使用迭代法，且由于二叉搜索树自带遍历条件，因此不需要额外空间。
//时间复杂度O(n)
//空间复杂度O(1)
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int L, int R) {
if (!root) return nullptr;
// 处理头结点，让root移动到[L, R] 范围内，注意是左闭右闭
while (root != nullptr && (root->val < L || root->val > R)) {
if (root->val < L) root = root->right; // 小于L往右走
else root = root->left; // 大于R往左走
}
TreeNode *cur = root;
// 此时root已经在[L, R] 范围内，处理左孩子元素小于L的情况
while (cur != nullptr) {
while (cur->left && cur->left->val < L) {
cur->left = cur->left->right;
}
cur = cur->left;
}
cur = root;
// 此时root已经在[L, R] 范围内，处理右孩子大于R的情况
while (cur != nullptr) {
while (cur->right && cur->right->val > R) {
cur->right = cur->right->left;
}
cur = cur->right;
}
return root;
}
};108.将有序数组转换为二叉搜索树
文档讲解：代码随想录将有序数组转换为二叉搜索树
视频讲解：手撕将有序数组转换为二叉搜索树
题目：
学习：
注意本题需要构造的不仅是二叉搜索树还需要是一颗平衡二叉树。平衡二叉树需要所有中间节点的左右孩子的高度差不大于1。
依据上述条件，又因为本题给的数组已经是一个升序排列的数组了，因此本题显然是从中间节点进行构造，每次取数组的中间节点，即可构造出平衡的二叉搜索树。注意如果数组是奇数，显然选中间的节点，如果数组是偶数则中间的两个节点选哪个都可以，只要统一就行，最后构造出的二叉树会有所区别，这也是本题答案不唯一的原因。
代码：
//时间复杂度O(n)
//空间复杂度O(n^2)
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
//确定终止条件
if(nums.size() == 0) return nullptr;
//取中间值
int mid = nums.size()/2;
TreeNode* node = new TreeNode(nums[mid]);
//左区间
vector<int> left(nums.begin(), nums.begin() + mid);
//右区间
vector<int> right(nums.begin() + mid + 1, nums.end());
//分配左右子树
node->left = sortedArrayToBST(left);
node->right = sortedArrayToBST(right);
return node;
}
};代码：不使用额外空间，下标确定数组区间
//时间复杂度O(n)
//空间复杂度O(n)递归产生的栈空间
class Solution {
public:
//不使用额外空间，下标法
TreeNode* traversal(vector<int>& nums, int left, int right) {
//确定终止条件(区间左闭右闭)
if(left > right) return nullptr;
//找到中间值
int mid = left + (right - left)/2; //防止数值越界
TreeNode* node = new TreeNode(nums[mid]);
//左区间
node->left = traversal(nums, left, mid - 1);
//右区间
node->right = traversal(nums, mid + 1, right);
return node;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
return traversal(nums, 0, nums.size() - 1);
}
};538.把二叉搜索树转换为累加树
文档讲解：代码随想录把二叉搜索树转换为累加树
视频讲解：手撕把二叉搜索树转换为累加树
题目：
学习：本题最重要的是需要找到它的规律，本题是将每个节点的新值转变为等于原树中大于或等于node.val的值之和。如果将二叉搜索树通过中序遍历转化为数组来看的话，其实就是从后往前依次累加。因此本题应该采用的遍历方法是反中序遍历，通过右中左的遍历顺序，因此将节点值累加。
注意本题累加过程中，采用的是双指针的方法，需要一个指向当前节点的前一个节点pre来保存上一个节点的累加和。
代码：
//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:
TreeNode* pre = nullptr; //指向当前节点的前一个节点
//本题不需要返回值，只用将当前值改变就行
void traversal(TreeNode* root) {
//终止条件
if(root == nullptr) return;
//本题的遍历顺序应该为右中左
//右
traversal(root->right);
//中
if(pre != nullptr) {
root->val = root->val + pre->val;
}
pre = root;
//左
traversal(root->left);
}
TreeNode* convertBST(TreeNode* root) {
traversal(root);
return root;
}
};代码：本题也能够使用迭代法进行
//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
private:
int pre; // 记录前一个节点的数值
void traversal(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* cur = root;
while (cur != NULL || !st.empty()) {
if (cur != NULL) {
st.push(cur);
cur = cur->right; // 右
} else {
cur = st.top(); // 中
st.pop();
cur->val += pre;
pre = cur->val;
cur = cur->left; // 左
}
}
}
public:
TreeNode* convertBST(TreeNode* root) {
pre = 0;
traversal(root);
return root;
}
};二叉树总结
对于二叉树来说我们首先需要掌握的就是递归这一算法，确定递归三部曲掌握通过递归进行的二叉树的前序遍历、中序遍历、后序遍历的方法。
其次对于二叉树来说，它的迭代方法同样也很重要，递归由于其不断递归的特殊性，稍有不慎就容易导致栈溢出，且问题相对于迭代法不好排查。因此掌握迭代法对于实际工程使用也十分重要。
这七天我们对二叉树的遍历方式，各种属性，二叉树的修改和构造都进行了详细的练习。并且对二叉树中一个重要的类型二叉搜索树也进行了详细的考察，二叉搜索树自带的遍历顺序，能够便于解答很多问题，同时对二叉搜索树进行中序遍历能够得到一个非递减序列也是重要的性质之一。
总结来说：
-
涉及到二叉树的构造，无论普通二叉树还是二叉搜索树一定都是先构造中节点。
-
求普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算。（包括是否对称，求最大深度，最小深度，有多少个节点，是否平衡，路径问题，左叶子之和、左下角的值等）
-
求二叉搜索树的属性，一定是中序了，要不白瞎了有序性了。
二叉树系列就这么完美结束了！
