【leetcode】998. Maximum Binary Tree II

题目如下：

We are given the root node of a maximum tree: a tree where every node has a value greater than any other value in its subtree.

Just as in the previous problem, the given tree was constructed from an 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 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:

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:

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:

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]

Note:

1 <= B.length <= 100

解题思路：本题的题意需要好好理解一番，大概意思是这样。给定树A的根节点，并且A是一个最大二叉树（最大二叉树的定义见题目中previous problem），根据特性将A还原成一个数组的表示，如用例1是[1,4,2,3]，在这个数组后面追加一个元素后变成[1,4,2,3,5]，再根据这个新得的数组构造出树B。那么解题方法也可以分成两部，先是还原成数组，这个用递归即可；二是构造树，见【leetcode】654. Maximum Binary Tree 。

代码如下：

# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution(object):

    def build(self, node, nums):

        v = max(nums)

        inx = nums.index(v)

        node.val = v

        ll = nums[:inx]

        rl = nums[inx + 1:]

        if len(ll) > 0:

            left = TreeNode(None)

            node.left = left

            self.build(left, ll)

        if len(rl) > 0:

            right = TreeNode(None)

            node.right = right

            self.build(right, rl)

    def decompile(self,node):

        if node == None:

            return []

        return self.decompile(node.left) + [node.val] + self.decompile(node.right)

    def insertIntoMaxTree(self, root, val):

        """

        :type root: TreeNode

        :type val: int

        :rtype: TreeNode

        """

        path = self.decompile(root) + [val]

        newRoot = TreeNode(None)

        self.build(newRoot, path)

        return newRoot

【leetcode】998. Maximum Binary Tree II的相关教程结束。