代码随想录算法训练营Day20|654. 最大二叉树、700. 二叉搜索树中的搜索、98. 验证二叉搜索树
654. 最大二叉树
注意题干信息：
- 整数数组
nums元素不重复：元素不重复意味着可以通过元素值唯一确定一个数组下标。
并且题目罗列了样例的递归过程，能明显发现递归函数的终止条件是if (vec.size() == 0) return NULL;，当然在vec.size()为1的时候，分割数组后的左右区间都为0，因此没有必要继续递归，可以使用该条件对递归逻辑进行剪枝：
if (vec.size() == 1) return node;
另外注意分割vector的边界是「左闭右开」，完整代码如下：
/**
* 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:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return traversal(nums);
}
TreeNode* traversal(vector<int> vec) {
if (vec.size() == 0) return NULL;
int maxIndex, maxValue = INT_MIN;
for (int i = 0; i < vec.size(); i++) {
if (vec[i] > maxValue) {
maxIndex = i;
maxValue = vec[i];
}
}
TreeNode* node = new TreeNode(maxValue);
// 剪枝部分遍历过程
if (vec.size() == 1) return node;
vector<int> leftVec(vec.begin(), vec.begin() + maxIndex);
vector<int> rightVec(vec.begin() + maxIndex + 1, vec.end());
node->left = traversal(leftVec);
node->right = traversal(rightVec);
return node;
}
};
②内存优化
这里每次递归会新建一个vector数组，造成额外的开销。注意类似用数组构造二叉树的题目，每次分隔尽量不要定义新的数组，而是通过下标索引直接在原数组上操作，这样可以节约时间和空间上的开销。
/**
* 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:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return traversal(nums, 0, nums.size());
}
// 区间为左开右闭
TreeNode* traversal(vector<int>& nums, int left, int right) {
// 因为数组长度不变，需要更换终止天剑
if (left >= right) return NULL;
int maxValue = INT_MIN, maxIndex;
// 原数组操作，注意循环边界
for (int i = left; i < right; i++) {
if (nums[i] > maxValue) {
maxIndex = i;
maxValue = nums[i];
}
}
TreeNode* node = new TreeNode(maxValue);
node->left = traversal(nums, left, maxIndex);
node->right = traversal(nums, maxIndex + 1, right);
return node;
}
};
617. 合并二叉树
/**
* 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:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
return traversal(root1, root2);
}
TreeNode* traversal(TreeNode* root1, TreeNode* root2) {
if (root1 == NULL && root2 == NULL) return NULL;
TreeNode* node = new TreeNode();
if (root1 == NULL && root2 != NULL) {
node->val = root2->val;
node->left = traversal(NULL, root2->left);
node->right = traversal(NULL, root2->right);
}
else if (root1 != NULL && root2 == NULL) {
node->val = root1->val;
node->left = traversal(root1->left, NULL);
node->right = traversal(root1->right, NULL);
}
else {
node->val = root1->val + root2->val;
node->left = traversal(root1->left, root2->left);
node->right = traversal(root1->right, root2->right);
}
return node;
}
};
其实递归的终止条件可以再精简一些，核心是将两树合并的结果赋值在t1上。因此我们不再新建节点来合并root1和root2的数值之和，直接覆盖root1的节点值。
root1->val = root1->val + root2->val;
root1->left = mergeTrees(root1->left, root2->left);
之前我们还会对两个根节点是否为NULL分别进行讨论，以此来调整根节点的值和其左/右孩子节点的构成，但其实只要一方节点为空就不需要进行节点的合并，直接返回非空节点，其左/右孩子节点保持原样即可。代码如下：
/**
* 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:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (root1 == NULL) return root2;
if (root2 == NULL) return root1;
root1->val = root1->val + root2->val;
root1->left = mergeTrees(root1->left, root2->left);
root1->right = mergeTrees(root1->right, root2->right);
return root1;
}
};
700. 二叉搜索树中的搜索
/**
* 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:
TreeNode* searchBST(TreeNode* root, int val) {
if (root == NULL) return NULL;
if (root->val == val) return root;
else if (root->val > val) return searchBST(root->left, val);
else return searchBST(root->right, val);
}
};
98. 验证二叉搜索树
这里很容易陷入误区，递归整颗二叉树，只要每个节点与其左右孩子节点满足BST的性质，即满足条件。
但二叉树的性质为：
-
节点的左子树只包含 小于 当前节点的数。
-
节点的右子树只包含 大于 当前节点的数。
-
所有左子树和右子树自身必须也是二叉搜索树。
可写出如下代码：
/**
* 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:
bool isValidBST(TreeNode* root) {
if (root == NULL) return true;
if (root->left) {
if (root->left->val >= root->val) return false;
isValidBST(root->left);
}
if (root->right) {
if (root->right->val <= root->val) return false;
isValidBST(root->right);
}
return true;
}
};
这样的思路只能保证根节点与其相邻的左/右孩子节点满足BST特性。不满足以下的情况：
7
/ \
2 8
/ / \
1 6 10
如图虽然8、6、10满足BST特性，但放眼根节点，其右侧却包含数值更小的非临近节点。所以需要思考其他的办法。
我们需要利用BST的特性，二叉搜索树的中序遍历是递增数组（因为二叉搜索树不能有重复的元素！！！）那么验证二叉搜索树的问题就被转换为了判断一个序列是不是递增。代码如下：
/**
* 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:
bool isValidBST(TreeNode* root) {
vector<int> vec;
if (root != NULL) traversal(root, vec);
for (int i = 0; i < vec.size() - 1; i++) {
// 因为不包含重复元素，只要有相等元素即验证失败！
if (vec[i] >= vec[i + 1]) return false;
}
return true;
}
void traversal(TreeNode* node, vector<int>& vec) {
if (node == NULL) return;
traversal(node->left, vec);
vec.push_back(node->val);
traversal(node->right, vec);
return;
}
};