654. 最大二叉树
思路：
思路跟106、105是一致的，先找出最大值，再根据最大值划分左右区间，左右区间再递归相同的操作，直到找到根节点。这里的左右区间即可以用新建的数组保存，再送入递归，也可以直接记录左右区间的下标，这样可以减少代码的冗余。
代码：
/**
* 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* gettree(vector<int>& nums)
{
TreeNode* node = new TreeNode(0);
if(nums.size()==1)
{
node->val=nums[0];
return node;
}
int maxnum=0;
int index=0;
for(int i=0;i<nums.size();i++)
{
if(nums[i]>maxnum)
{
maxnum=nums[i];
index=i;
}
}
node->val=maxnum;
if(index>0)
{
vector<int> leftvector(nums.begin(),nums.begin()+index);
node->left=gettree(leftvector);
}
if(index<nums.size()-1)
{
vector<int> rightvector(nums.begin()+index+1,nums.end());
node->right=gettree(rightvector);
}
return node;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return gettree(nums);
}
};
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* gettree(TreeNode* tree1, TreeNode* tree2)
{
if(tree1==NULL) return tree2;
if(tree2==NULL) return tree1;
TreeNode* root=new TreeNode(0);
root->val= tree1->val+tree2->val;
root->left=gettree(tree1->left,tree2->left);
root->right=gettree(tree1->right,tree2->right);
return root;
}
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
return gettree(root1,root2);
}
};
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* search(TreeNode* pointer, int val)
{
if(pointer==NULL||pointer->val==val)return pointer;
TreeNode* res=NULL;
if(val<pointer->val)
{
res=search(pointer->left,val);
}
if(val>pointer->val)
{
res=search(pointer->right,val);
}
return res;
}
TreeNode* searchBST(TreeNode* root, int val) {
return search(root,val);
}
};
（迭代法）
/**
* 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) {
while(root!=NULL)
{
if(val<root->val)
{
root=root->left;
}
else if(val>root->val)
{
root=root->right;
}else if(val==root->val)
{
return root;
}
}
return NULL;
}
};
98. 验证二叉搜索树
思路：
因为二叉搜索树的左边一定要比中间小，中间一定要比右边小，所以如果把所有的数值放进一个数组里，那么该数组就是一个单调递增的数组。运用该思路，在采用中序遍历的基础上，可以直接去比较当前节点和前一个节点的值，如果满足单调递增，则说明是，否则就不是。
代码：
/**
* 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* 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;
}
};
