今日的四道题目分别是
- 重叠二叉树
- 在已知二叉树中搜索并返回以给定值为根节点的二叉树
- 判断二叉树是否是二叉搜索树
- 在给定数组中重建最大二叉树
最大二叉树
题目理解：
给定一个数组，其中最大的数作为根，根左边的数组构造左子树，根右边的数组构造右子树。
代码实现：
class Solution {
public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {TreeNode*node = new TreeNode(0);if(nums.size()==1){node->val=nums[0];return node;}int index =0;int maxValue =nums[0] ;for(int i=0;i<nums.size();i++){if(nums[i] >maxValue){maxValue=nums[i];index =i;}}//TreeNode* node = new TreeNode(0);node->val=maxValue;if(index>0) {vector<int> vec(nums.begin(),nums.begin()+index);//区间构造函数node->left = constructMaximumBinaryTree(vec);}if(index<(nums.size()-1)) {vector<int> vec(nums.begin()+index+1,nums.end());node->right = constructMaximumBinaryTree(vec);}return node;}
};
其中，区间构造这块：这个if条件的区分左右区间很没有道理
if (index > 0) {vector<int> vec1(nums.begin(), nums.begin() + index); // 区间构造函数node->left = constructMaximumBinaryTree(vec1);}if (index < (nums.size() - 1)) {vector<int> vec2(nums.begin() + index + 1, nums.end());node->right = constructMaximumBinaryTree(vec2);}
重叠合并二叉树
题目理解：
已知两个二叉树，构造一个新的二叉树，新二叉树节点上的值是两个二叉树节点值的和。
代码实现：
class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if(root1==NULL) return root2;if(root2==NULL) return root1;root1->val+=root2->val;root1->left=mergeTrees(root1->left, root2->left);root1->right=mergeTrees( root1->right, root2->right);return root1;}
};
验证二叉搜索树
题目理解：
判断一棵二叉树是否满足：左子树所有的值都小于根节点，右子树所有的值都大于根节点。
代码实现：
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;}
};
搜索二叉搜索树
题目理解：
在给定二叉树中找到给点根节点的二叉树。
代码实现：
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(root==NULL||root->val==val) return root;if(root->val>val)return searchBST(root->left,val);if(root->val<val)return searchBST(root->right,val);return NULL;}
};