代码随想录Day17_二叉树

今日的四道题目分别是

1. 重叠二叉树
2. 在已知二叉树中搜索并返回以给定值为根节点的二叉树
3. 判断二叉树是否是二叉搜索树
4. 在给定数组中重建最大二叉树

最大二叉树

题目理解：

给定一个数组，其中最大的数作为根，根左边的数组构造左子树，根右边的数组构造右子树。

代码实现：

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;}
};