2026.03.13 02.13 第十七天
654 最大二叉树
本题难度不大，在前一天的基础上很快就能够写出来。
可以注意一下标准库提供的查找最大值的方法和区间范围控制
使用了中间节点，就要在传入右边区间的时候起始值多加一。
class Solution {
private:TreeNode* travelsal(vector<int>& nums, int begin, int end) {// 1. 基准情况：如果区间为空，返回空if (begin >= end) return nullptr;// 2. 找到当前区间的最大值及其下标auto it_begin = nums.begin() + begin;auto it_end = nums.begin() + end;auto maxIt = std::max_element(it_begin, it_end);int maxIndex = std::distance(nums.begin(), maxIt);// 3. 构建当前根节点TreeNode* root = new TreeNode(*maxIt);// 4. 递归构建左右子树// 左区间：[begin, maxIndex)root->left = travelsal(nums, begin, maxIndex);// 右区间：[maxIndex + 1, end) <-- 注意这里必须 +1root->right = travelsal(nums, maxIndex + 1, end);return root;}public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {return travelsal(nums, 0, nums.size());}
};
617 合并二叉树
这题很简单，每次传入两个节点，遍历即可
新树能不能直接使用旧树的节点是个问题
递归法：
class Solution {
public:TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1// 修改了t1的数值和结构t1->val += t2->val; // 中t1->left = mergeTrees(t1->left, t2->left); // 左t1->right = mergeTrees(t1->right, t2->right); // 右return t1;}
};
迭代法使用队列模拟层序遍历即可。
700 二叉搜索树中的搜索
比较简单
迭代法非常符合直觉，实现也很简单，由于二叉搜索树本身的性质，不需要借助栈来实现。
迭代法：
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(root == nullptr) return nullptr;while(root) {if(root->val == val) {return root;}else if(root->val < val) {root = root->right;}else {root = root->left;}}return nullptr;}
};
递归法：
也很简单~
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(root == nullptr || root->val == val) return root;TreeNode* result = nullptr;if(root->val < val) result = searchBST(root->right, val);if(root->val > val) result = searchBST(root->left, val);return result;}
};
28 验证二叉搜索树
递归法先使用中序遍历，利用中序遍历结果是从小到大序列的性质，生成数组，验证数组是否是严格从小到大即可。
class Solution {
private:vector<int> vec;void travelsal(TreeNode* node) {if(node == nullptr) return;travelsal(node->left);vec.push_back(node->val);travelsal(node->right);}public:bool isValidBST(TreeNode* root) {travelsal(root);for(int i = 0; i < vec.size() - 1; i++) {if(vec[i] >= vec[i + 1]) return false;}return true;}
};
如果直接在递归过程中比较，会有几个大坑，需要注意！！！
另一种迭代法：
class Solution {
public:TreeNode* pre = NULL; // 用来记录前一个节点bool isValidBST(TreeNode* root) {if (root == NULL) return true;bool left = isValidBST(root->left);if (pre != NULL && pre->val >= root->val) return false;pre = root; // 记录前一个节点bool right = isValidBST(root->right);return left && right;}
};
有一点理解难度，利用了中序遍历，二叉搜索树前一个节点值始终小于后一个的特点。
迭代法思路相同。