654.最大二叉树
虽然说昨晚没做那道靠前序后序写出真正二叉树的题，但是今天这道题也用了昨天那个思路，比昨天那题还能简单些。我参照了昨天题的答案一遍就写出来了（犯了个小错误，就是nums.size()等于1的时候，我开始return 的是nums[0]，但我的意思其实是root）
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
if(nums.size() == 0){
return nullptr;
}
if(nums.size() == 1){
TreeNode* root = new TreeNode(nums[0]);
return root;
}
int max_val = INT_MIN;
int cut_index = -1;
for(int i=0; i<nums.size(); i++){
if(max_val < nums[i]){
max_val = nums[i];
cut_index = i;
}
}
TreeNode* root = new TreeNode(nums[cut_index]);
vector<int> left_arr(nums.begin(), nums.begin()+cut_index);
vector<int> right_arr(nums.begin()+cut_index+1, nums.end());
root->left = constructMaximumBinaryTree(left_arr);
root->right = constructMaximumBinaryTree(right_arr);
return root;
}
};
617.合并二叉树
这道题很轻松的写出来了。虽然说这道题之前做过，但我这遍写的时候并没看之前的答案。我觉得好像是稍微会一点递归了。
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if((root1 == nullptr) && (root2 == nullptr)){
return nullptr;
}
if(root1 == nullptr){
return root2;
}
if(root2 == nullptr){
return root1;
}
TreeNode* root = new TreeNode(root1->val + root2->val);
root->left = mergeTrees(root1->left,root2->left);
root->right = mergeTrees(root1->right,root2->right);
return root;
}
};
700.二叉搜索树中的搜索
慢慢的会写了。倒也是因为这道题非常简单。
但还是犯了小错误。开始的时候没有设TreeNode* res，所以就算找到了返回的值都是nullptr。这个错误好像之前刷二叉树题的时候就犯过。如果没有res来接着递归return回来的值，那程序怎么知道答案是多少呢。
我提交后，还看到了之前写的答案。也就是在几个月前，那时候我用的while loop来找的值。本质上没有错误，只不过当时的我可能还没太搞清楚递归。我觉得我还是进步了一些的。
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if(root == nullptr){
return nullptr;
}
TreeNode* res;
if(root->val == val){
return root;
}
if(root->val > val){
res = searchBST(root->left,val);
}
if(root->val < val){
res = searchBST(root->right,val);
}
return res;
}
};
98.验证二叉搜索树
写之前看到了Carl提示说这道题得用中序遍历，但是没想到为什么要什么写。自己写了一个答案，但是一运行发现不对。
我写的这个只能判断当前的left和right与父节点的关系是否正确，但是看不出来整体是不是对的。
class Solution {
public:
bool isValidBST(TreeNode* root) {
if(root == nullptr){
return true;
}
if((root->left == nullptr) && (root->right == nullptr)){
return true;
}
bool res;
if((root->left != nullptr) && (root->left->val >= root->val)){
return false;
}
if((root->right != nullptr) && (root->right->val <= root->val)){
return false;
}
if((root->left != nullptr) && (root->right != nullptr) &&
(root->right->val > root->val) && (root->left->val < root->val)){
res = true;
}
return res&&isValidBST(root->left)&&isValidBST(root->right);
}
};
想了半天没想明白。看了答案，原来是直接中序历遍把结果都输出。然后看输出的数组是不是有序的。给想复杂了。之所以我自己没想到，是我一直用的错误的二叉搜索树来推导。 其实下面这个是我想做得，但是我没写出来，发现原来写出来的话这么简单。
class Solution {
public:
TreeNode* pre=nullptr;
bool isValidBST(TreeNode* root) {
if(root == nullptr)
return true;
bool left = isValidBST(root->left);
if((pre != nullptr) && (pre->val >= root->val)){
return false;
}
pre = root;
bool right = isValidBST(root->right);
return left && right;
}
};
