[数据结构与算法]【leetcode】【2022/8/30】998. 最大二叉树 II

问题描述：

• 给定最大树的根节点 root 和一个整数 val。
  • 最大树定义为：满足其中每个节点的值都大于其子树中的任何其他值的一棵树。
• 该题的前导题为 leetcode 654 最大二叉树。【做 998 前最好做一遍 654】
  • 654 中用一个数组来构造一棵最大数。
• 该题 998 中给定的 root 正是由 654 中的数组构造而成。
  • 而该题的问题就是，假设 root 由数组 a 构成，在数组 a 的末尾加上一个数 val 构成数组 b，返回由数组 b 构成的最大树。

核心思路：

• 该题题意其实并不难理解（虽然写了一大堆有的没的定义），但是需要先做了 leetcode 654，有了 654 的基础，该题的解题就比较容易想。
  • 654 其实就是用一个数组 a 构建了最大树 root；998 其实就是问给定 root，往 root 代表的数组 a 末尾插入一个值 val 组成新的数组 b，返回 b 构建的最大树。
• 自然是不需要重新构建数组 b 来重新构建最大树，只需要遍历最大树找到相应的插入位置即可，更进一步来说，只需要从根节点开始一直往右遍历就可以找到插入位置。
  • 这个解题思路是很自然的事，因为插入值 val 处于数组 b 的末尾，那它插入后只可能是根节点开始一直往右遍历过程中某个节点的父节点。所以只需要一直访问右子节点，直到找到值低于 val 的第一个节点。【找到该节点后，在该节点与其父节点之间插入值即可】
• 该题可以用迭代和递归的方法来解题。

代码实现：

• 迭代解法代码实现如下：

  class Solution
  {
  public:
      TreeNode* insertIntoMaxTree(TreeNode* root, int val)
      {
          TreeNode* node = new TreeNode(val);
          TreeNode* cur = root; // cur 用来不断访问右子节点
          TreeNode* pre = nullptr; // pre 用来记录 cur 的父节点
          while(cur)
          {
              if(cur->val < val) // 如果不断访问的右子节点中存在值低于插入值
              {
                  if(pre) pre->right = node; // 断开 cur 与 其父节点 pre 的关联
                  else root = node; // 如果来到此步，说明插入值是新的 head
                  node->left = cur; // 将 插入节点 指向 当前节点 cur
                  break;
              }
              pre = cur;
              cur = cur->right;
          }
          if(!cur) // 如果访问完右子节点都没有找到插入位置，则说明 val 是数组后半段的最小值
              pre->right = node;
          return root;
      }
  };
  

• 递归解法代码实现如下：【贴自评论区，其实思路是一样的，不断访问右子节点】

  class Solution {
  public:
      TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
          if (!root || root->val < val) // 如果访问完或者当前值低于插入值，则放置节点
            return new TreeNode(val, root, nullptr);
          root->right = insertIntoMaxTree(root->right, val);
          return root;
      }
  };