代码随想录第二十二天 | 654.最大二叉树, 617.合并二叉树, 700.二叉搜索树中的搜索, 98. 验证二叉搜索树

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;