654.最大二叉树

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

• 确定递归函数的参数和返回值

  参数传入的是存放元素的数组，返回该数组构造的二叉树的头结点，返回类型是指向节点的指针。

  TreeNode* constructMaximumBinaryTree(vector& nums)
  

  • 确定终止条件

    题目中说了输入的数组大小一定是大于等于1的，所以我们不用考虑小于1的情况，那么当递归遍历的时候，如果传入的数组大小为1，说明遍历到了叶子节点了

    那么应该定义一个新的节点，并把这个数组的数值赋给新的节点，然后返回这个节点。 这表示一个数组大小是1的时候，构造了一个新的节点，并返回

    TreeNode* node = new TreeNode(0);
    if (nums.size() == 1) {
        node->val = nums[0];
        return node;
    }
    

    • 确定单层递归的逻辑

      这里有三步工作

      1. 先要找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组

      int maxValue = 0;
      int maxValueIndex = 0;
      for (int i = 0; i < nums.size(); i++) {
          if (nums[i] > maxValue) {
              maxValue = nums[i];
              maxValueIndex = i;
          }
      }
      TreeNode* node = new TreeNode(0);
      node->val = maxValue;
      

      2. 最大值所在的下标左区间 构造左子树

         这里要判断maxValueIndex > 0，因为要保证左区间至少有一个数值

      if (maxValueIndex > 0) {
          vector newVec(nums.begin(), nums.begin() + maxValueIndex);
          node->left = constructMaximumBinaryTree(newVec);
      }
      

      3. 最大值所在的下标右区间 构造右子树

         判断maxValueIndex < (nums.size() - 1)，确保右区间至少有一个数值

      if (maxValueIndex < (nums.size() - 1)) {
          vector newVec(nums.begin() + maxValueIndex + 1, nums.end());
          node->right = constructMaximumBinaryTree(newVec);
      }
      

      这样我们就分析完了，整体代码如下：（详细注释）

      class Solution {
      public:
          TreeNode* constructMaximumBinaryTree(vector& nums) {
              TreeNode* node = new TreeNode(0);
              if(nums.size() == 1){
                  node->val = nums[0];
                  return node;
              } 
              // 找到数组中最大的值和对应的下标
              int maxValue = nums[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 newVec(nums.begin(), nums.begin() + maxValueIndex);
                  node->left = constructMaximumBinaryTree(newVec);
              }
              // 最大值所在的下标右区间 构造右子树
              if(maxValueIndex < nums.size() - 1){
                  vector newVec(nums.begin() + 1 + maxValueIndex, nums.end());
                  node->right = constructMaximumBinaryTree(newVec);
              }
              
              return node;
          }
      

      617.合并二叉树

      使用队列，模拟的层序遍历，代码如下：

      class Solution {
      public:
          TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
              if(root1 == NULL) return root2;
              if(root2 == NULL) return root1;
              
              queue que;
              que.push(root1);
              que.push(root2);
              while(!que.empty()){
                  TreeNode* node1 = que.front();
                  que.pop();
                  TreeNode* node2 = que.front();
                  que.pop();
                  node1->val += node2->val;
                  
                  if(node1->left != NULL && node2->left != NULL){
                      que.push(node1->left);
                      que.push(node2->left);
                  }
                  if(node1->right != NULL && node2->right != NULL){
                      que.push(node1->right);
                      que.push(node2->right);
                  }
                  if(node1->left == NULL && node2->left != NULL){
                      node1->left = node2->left;
                  }
                  if(node1->right == NULL && node2->right != NULL){
                      node1->right =node2->right;
                  }
              }
              return root1;
          }
      };
      

      700.二叉搜索树中的搜索

      class Solution {
      public:
          TreeNode* searchBST(TreeNode* root, int val) {
              TreeNode* node = root;
              while(node != NULL ){
                  if(node->val > val) {
                      node = node->left;
                  } else if (node->val < val) {
                      node = node->right;
                  } else{
                      return node;
                  }
              }
              return NULL;
          }
      };