654.最大二叉树

看完想法：构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树

确定递归函数的参数和返回值:返回TreeNode* 输入vector<int>& num; 确定终止条件:当输入数组大小=1的时候，传入数值；确定单层递归的逻辑：和之前的题目有一些相似

if的意义是保证左右区间至少有一个元素，如果没有就不执行了，缺少if，构造vector会报错

TreeNode* constructMaximumBinaryTree(vector<int>& nums) {//终止条件TreeNode* node = new TreeNode(0);if(nums.size() == 1){node->val = nums[0];return node;}//先找最大值，即根节点int maxValue = 0;int maxValueIndex = 0;for(int i=0; i<nums.size(); i++){if(maxValue < nums[i]){maxValue = nums[i];maxValueIndex = i;}}node->val = maxValue;if (maxValueIndex > 0) {vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);node->left = constructMaximumBinaryTree(newVec);}// 最大值所在的下标右区间 构造右子树// if的意义是保证左右区间至少有一个元素，如果没有就不执行了，缺少if，构造vector会报错if (maxValueIndex < (nums.size() - 1)) {vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());node->right = constructMaximumBinaryTree(newVec);}return node;}

617.合并二叉树

看完想法：感觉还挺简单的，这里注意一下终止条件和递归的逻辑

TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if(root1 == NULL) return root2;if(root2 == NULL) return root1;root1->val = root1->val + root2->val;root1->left = mergeTrees(root1->left, root2->left);root1->right = mergeTrees(root1->right, root2->right);return root1;}

700.二叉搜索树中的搜索

看完想法：要先注意什么是二叉搜索树，之前的基本知识里面有提到过：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

• 因为二叉搜索树的节点是有序的，所以可以有方向的去搜索。

• 如果root->val > val，搜索左子树，如果root->val < val，就搜索右子树，最后如果都没有搜索到，就返回NULL。

  递归和迭代 都可以掌握以下

   TreeNode* searchBST(TreeNode* root, int val) {if(root == NULL || root->val == val) return root;TreeNode* result = NULL;if(root->val > val) result = searchBST(root->left, val);if(root->val < val) result = searchBST(root->right, val);return result;

  98. 验证二叉搜索树

  看完想法：如果是空节点 是不是二叉搜索树呢？是的，二叉搜索树也可以为空！最直观的解法是：把二叉树用中序遍历转为数组输出，然后遍历数组，看是不是单调递增的(等于的情况也不是二叉搜索树了)

  vector<int> vec;void traversal(TreeNode* root) {if (root == NULL) return;traversal(root->left);vec.push_back(root->val); // 将二叉搜索树转换为有序数组traversal(root->right);}
  public:bool isValidBST(TreeNode* root) {vec.clear(); // 不加这句在leetcode上也可以过，但最好加上traversal(root);for (int i = 1; i < vec.size(); i++) {// 注意要小于等于，搜索树里不能有相同元素if (vec[i] <= vec[i - 1]) return false;}return true;