最大二叉树

题目链接：力扣

这题 和昨天 根据前序中序（后序中序）构造二叉树题目的思想是一样的。
先找到nums中的最大值，再根据最大值的位置将其余节点划分为左右子树，在这过程中要注意左右子树保持左闭右开区间。
注意递归法时，终止条件为“传入的数组大小为1”，也就是说numsbegin == numsend，此时说明已经遍历到了叶子节点。 

class Solution {
public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {return traversal(nums,0,nums.size());}TreeNode* traversal(vector<int>& nums, int numsbegin, int numsend){if(numsbegin == numsend) return nullptr;int index = numsbegin;int maxvalue = INT_MIN;for(int i=numsbegin; i<numsend;i++)    //寻找nums中的最大值{if(nums[i] > maxvalue){maxvalue = nums[i];index = i;}            }TreeNode* midNode = new TreeNode(maxvalue);//遵循左闭右开int leftbegin = numsbegin;int leftend = index;int rightbegin = index+1;int rightend = numsend;midNode->left = traversal(nums,leftbegin,leftend);midNode->right = traversal(nums,rightbegin,rightend);return midNode;}
};

合并二叉树

题目链接：力扣

 遍历两个树和遍历一个树逻辑是一样的，只不过传入两个树的节点，同时操作
这里采用前序遍历比较好理解。

class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {return traversal(root1, root2);        }TreeNode* traversal(TreeNode* cur1, TreeNode* cur2){if(!cur1 && !cur2) return nullptr;else if(!cur1 && cur2) return cur2;else if(cur1 && !cur2) return cur1;int NodeVal = cur1->val + cur2->val;TreeNode* Node = new TreeNode(NodeVal);Node->left = traversal(cur1->left, cur2->left);Node->right = traversal(cur1->right,cur2->right);return Node;}
};

二叉搜索树中的搜索

题目链接： 力扣

做这道题目 要重复利用好二叉搜索树的性质 ，二叉搜索树的节点是有序的，所以可以有方向的去搜索。

二叉搜索树是一个有序树：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉搜索树

递归法：

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

迭代法：
二叉搜索树的特殊性就是节点的有序性，所以可以不使用辅助栈或者队列就可以写出迭代法。

    TreeNode* searchBST(TreeNode* root, int val){while(root){if(root->val < val)root = root->right;else if(root->val > val)root = root->left;elsereturn root;}return nullptr;}

验证二叉搜索树 

题目链接：力扣 

知识点：在中序遍历下，输出的二叉搜索树节点的数值是有序序列。
即验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。

在写这道题之初，我掉入了一个陷阱，即单纯的比较了左节点小于中间节点，右节点大于中间节点。即

//错误示例！！！
bool isValidBST1(TreeNode* root) {       if(!root) return true;bool left = root->left && root->left->val < root->val;bool right = root->right && root->right->val > root->val;if((!root->left && !root->right) ||(!root->left && right) || (left && !root->right)||(left && right))return isValidBST(root->left) && isValidBST(root->right);elsereturn false;}

但是，我们应该要做的是 比较左子树所有节点小于中间节点，右子树所有节点大于中间节点

例如上图中的树就不属于二叉搜索树！

正确代码：

    long long maxVal = LONG_MIN;bool isValidBST(TreeNode* root) {    if(!root) return true;bool leftBST = isValidBST(root->left);if(maxVal < root->val)  maxVal = root->val;else return false;bool rightBST = isValidBST(root->right);return (leftBST && rightBST);}