链接：https://leetcode.cn/problems/maximum-binary-tree-ii/solution/-by-xun-ge-v-r5uq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

示例

思路

解题思路
关于树的相关问题使用递归基本上都可以解决

本题并不难，感觉难点在于读懂题目。

题目给定的根节点是由一个数组a根据最大树规则构造的一个最大树，在数组a后面加一个元素返回重新构造之后的最大树
【暴力解法】
那就简单了，暴力解法就是先使用中序遍历将根节点转化为数组a，再在数组a后面添加一个元素转化为数组b，然后再将数组b转化为最大树，转化规则题目都给定了，直接使用递归按题目给定要求构造即可

【利用最大树性质】
很显然暴力解法时间消耗大，而且繁琐。那么有没有简单一些的方法呢，当然有。
我们可以利用最大树规则性质，可以发现在数组a后面添加一个元素数组b

• 如果这个元素val比数组a最大值(其实就是根节点)大，那么val左边的元素(其实就是当前根节点的子孙节点)都是val的左节点
• 如果这个元素val比数组a最大值(其实就是根节点)小，那么val肯定是当前根节点的右节点
• 利用上面性质递归即可，需要细细品味

代码注释超级详细

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


struct TreeNode* insertIntoMaxTree(struct TreeNode* root, int val){
    //如果这个元素val比数组a最大值(其实就是根节点)大
    //那么val左边的元素(其实就是当前根节点的子孙节点)都是val的左节点

    //当前节点不存在，那肯定就比val小
    if(!root || root->val < val)
    {
        struct TreeNode* node = (struct TreeNode* )calloc(1, sizeof(struct TreeNode));
        node->val = val;
        node->left = root;
        return node;
    }
    //如果这个元素val比数组a最大值(其实就是根节点)小
    //那么val肯定是当前根节点的右节点
    root->right = insertIntoMaxTree(root->right, val);
    return root;
}

作者：xun-ge-v
链接：https://leetcode.cn/problems/maximum-binary-tree-ii/solution/-by-xun-ge-v-r5uq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。