998. Maximum Binary Tree II

爱被打了一巴掌 2024-04-08 09:28 77阅读 0赞

A **maximum tree** is a tree where every node has a value greater than any other value in its subtree.

You are given the `root` of a maximum binary tree and an integer `val`.

Just as in the [previous problem][], the given tree was constructed from a list `a` (`root = Construct(a)`) recursively with the following `Construct(a)` routine:

*  If `a` is empty, return `null`.
 *  Otherwise, let `a[i]` be the largest element of `a`. Create a `root` node with the value `a[i]`.
 *  The left child of `root` will be `Construct([a[0], a[1], ..., a[i - 1]])`.
 *  The right child of `root` will be `Construct([a[i + 1], a[i + 2], ..., a[a.length - 1]])`.
 *  Return `root`.

Note that we were not given `a` directly, only a root node `root = Construct(a)`.

Suppose `b` is a copy of `a` with the value `val` appended to it. It is guaranteed that `b` has unique values.

Return `Construct(b)`.

**Example 1:**

![f92e0c5b0f987e9759b9c58b04d7614c.jpeg][]

Input: root = [4,1,3,null,null,2], val = 5
    Output: [5,4,null,1,3,null,null,2]
    Explanation: a = [1,4,2,3], b = [1,4,2,3,5]

**Example 2:**

![3edbe77d42b0fc74f6ed5e15819b15b6.jpeg][]

Input: root = [5,2,4,null,1], val = 3
    Output: [5,2,4,null,1,null,3]
    Explanation: a = [2,1,5,4], b = [2,1,5,4,3]

**Example 3:**

![7e80bee7e1792445784c31cc6e6d7334.jpeg][]

Input: root = [5,2,3,null,1], val = 4
    Output: [5,2,4,null,1,3]
    Explanation: a = [2,1,5,3], b = [2,1,5,3,4]

题目：创建最大树，给定一颗最大二叉树，和一个值val, 将val以最右的形式插入二叉树。

思路：因为val是在构建二叉树的数组最后，因此在二叉树中往右子树找，找到最后一个比val大的节点。将其右子树改为新建节点的左子树，新建节点为其右子节点。代码：

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
            TreeNode* node = new TreeNode(val);
            if(root && root->val < val) {
                node->left = root;
                return node;
            }
            TreeNode* nd = root;
            while(nd && nd->right && nd->right->val > val)
                nd = nd->right;
            node->left = nd->right;
            nd->right = node;
            return root;
        }
    };

[previous problem]: https://leetcode.com/problems/maximum-binary-tree/
[f92e0c5b0f987e9759b9c58b04d7614c.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/da80acd9ebe3402aa2c138894f6b4e33.jpeg
[3edbe77d42b0fc74f6ed5e15819b15b6.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/8e82511b64b84766b2de393dede5adac.jpeg
[7e80bee7e1792445784c31cc6e6d7334.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/4819f51fa6b3497884f39021a2a4b3c1.jpeg