【C++代码】最大二叉树，合并二叉树，二叉搜索树中的搜索，验证二叉搜索树--代码随想录

题目：最大二叉树

• 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
  • 创建一个根节点，其值为 nums 中的最大值。
  • 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  • 递归地在最大值 右边 的 子数组后缀上 构建右子树。

题解

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

  • 确定递归函数的参数和返回值：参数传入的是存放元素的数组，返回该数组构造的二叉树的头结点，返回类型是指向节点的指针。

  • 确定终止条件：题目中说了输入的数组大小一定是大于等于1的，所以我们不用考虑小于1的情况，那么当递归遍历的时候，如果传入的数组大小为1，说明遍历到了叶子节点了。那么应该定义一个新的节点，并把这个数组的数值赋给新的节点，然后返回这个节点。 这表示一个数组大小是1的时候，构造了一个新的节点，并返回。

  • 确定单层递归的逻辑

    • 先要找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组。
    • 最大值所在的下标左区间 构造左子树
    • 最大值所在的下标右区间 构造右子树

  • class Solution {
    public:
        TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
            TreeNode* temp_node = new TreeNode(0);
            if(nums.size()==1){
                temp_node->val=nums[0];
                return temp_node;
            }
            int maxval=0;
            int maxvalindex=0;
            for(int i=0;i<nums.size();i++){
                if(nums[i]>maxval){
                    maxval=nums[i];
                    maxvalindex=i;
                }
            }
            temp_node->val=maxval;
            if(maxvalindex>0){
                vector<int> leftvec(nums.begin(),nums.begin()+maxvalindex);
                temp_node->left=constructMaximumBinaryTree(leftvec);
            }
            if(maxvalindex<(nums.size()-1)){
                vector<int> rightvec(nums.begin()+maxvalindex+1,nums.end());
                temp_node->right=constructMaximumBinaryTree(rightvec);
            }
            return temp_node;
        }
    };
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28

• 注意类似用数组构造二叉树的题目，每次分隔尽量不要定义新的数组，而是通过下标索引直接在原数组上操作，这样可以节约时间和空间上的开销。一般情况来说：如果让空节点（空指针）进入递归，就不加if，如果不让空节点进入递归，就加if限制一下， 终止条件也会相应的调整。

  • TreeNode* searsh(vector<int>& nums,int left,int right){
            if(left>=right){
                return nullptr;
            }
            int maxvalindex=left;
            for(int i=left+1;i<right;i++){
                if(nums[i]>nums[maxvalindex])
                    maxvalindex=i;
            }
            TreeNode* root=new TreeNode(nums[maxvalindex]);
            root->left=searsh(nums,left,maxvalindex);
            root->right=searsh(nums,maxvalindex+1,right);
            return root;
        }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14

题目：合并二叉树

• 给你两棵二叉树： root1 和 root2 。当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。返回合并后的二叉树。注意: 合并过程必须从两个树的根节点开始。

题解

• 深度优先搜索：可以使用深度优先搜索合并两个二叉树。从根节点开始同时遍历两个二叉树，并将对应的节点进行合并。两个二叉树的对应节点可能存在以下三种情况，对于每种情况使用不同的合并方式。

  • 如果两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空；
  • 如果两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点；
  • 如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和，此时需要显性合并两个节点。

• 对一个节点进行合并之后，还要对该节点的左右子树分别进行合并。这是一个递归的过程。

• class Solution {
  public:
      TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
          if(root1==nullptr){
              return root2;
          }
          if(root2==nullptr){
              return root1;
          }
          auto meged=new TreeNode(root1->val+root2->val);
          meged->left=mergeTrees(root1->left,root2->left);
          meged->right=mergeTrees(root1->right,root2->right);
          return meged;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15

• 时间复杂度：O(min⁡(m,n))，其中 m 和 n 分别是两个二叉树的节点个数。对两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应节点都不为空时才会对该节点进行显性合并操作，因此被访问到的节点数不会超过较小的二叉树的节点数。

• 空间复杂度：O(min⁡(m,n))，其中 m 和 n 分别是两个二叉树的节点个数。空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数。

• 那么中序遍历也是可以的，代码如下：

  • class Solution {
    public:
        TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
            if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2
            if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1
            // 修改了t1的数值和结构
            t1->left = mergeTrees(t1->left, t2->left);      // 左
            t1->val += t2->val;                             // 中
            t1->right = mergeTrees(t1->right, t2->right);   // 右
            return t1;
        }
    };
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12

• 后序遍历依然可以，代码如下：

  • class Solution {
    public:
        TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
            if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2
            if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1
            // 修改了t1的数值和结构
            t1->left = mergeTrees(t1->left, t2->left);      // 左
            t1->right = mergeTrees(t1->right, t2->right);   // 右
            t1->val += t2->val;                             // 中
            return t1;
        }
    };
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12

题目：二叉搜索树中的搜索

• 给定二叉搜索树（BST）的根节点 root 和一个整数值 val。你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

题解

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

• 一提到二叉树遍历的迭代法，可能立刻想起使用栈来模拟深度遍历，使用队列来模拟广度遍历。对于二叉搜索树可就不一样了，因为二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法。对于一般二叉树，递归过程中还有回溯的过程，例如走一个左方向的分支走到头了，那么要调头，在走右分支。而对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向。

• class Solution {
  public:
      TreeNode* searchBST(TreeNode* root, int val) {
          while(root!=nullptr){
              if(root->val>val){
                  root=root->left;
              }else if(root->val<val){
                  root=root->right;
              }else{
                  return root;
              }
          }
          return nullptr;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15

• 确定递归函数的参数和返回值,递归函数的参数传入的就是根节点和要搜索的数值，返回的就是以这个搜索数值所在的节点。

• 确定终止条件，如果root为空，或者找到这个数值了，就返回root节点。

• 确定单层递归的逻辑，如果root->val > val，搜索左子树，如果root->val < val，就搜索右子树，最后如果都没有搜索到，就返回NULL。

• class Solution {
  public:
      TreeNode* searchBST(TreeNode* root, int val) {
          if(root==nullptr||root->val==val){
              return root;
          }
          if(root->val>val){
              return searchBST(root->left,val);
          }
          if(root->val<val){
              return searchBST(root->right,val);
          }
          return nullptr;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15

题目：验证二叉搜索树

• 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下：节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。

题解

• 要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。

• class Solution {
  public:
      vector<int> temp_vec;
      void trave(TreeNode *root){
          if(root==nullptr)
          return;
          trave(root->left);
          temp_vec.push_back(root->val);
          trave(root->right);
      }
      bool isValidBST(TreeNode* root) {
          temp_vec.clear();
          trave(root);
          for(int i=1;i<temp_vec.size();i++){
              if(temp_vec[i]<=temp_vec[i-1])
              return false;
          }
          return true;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20

• 可以用迭代法模拟二叉树中序遍历，

•     bool isValidBST(TreeNode* root) {
          stack<TreeNode*> st;
          TreeNode* cur=root;
          TreeNode* pre=nullptr;
          while(cur!=nullptr||!st.empty()){
              if(cur!=nullptr){
                  st.push(cur);
                  cur=cur->left;
              }else{
                  cur=st.top();
                  st.pop();
                  if(pre!=nullptr&&cur->val<=pre->val){
                      return false;
                  }
                  pre=cur;
                  cur=cur->right;
              }
          }
          return true;
      }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20