Leetcode 998 Maximum Binary Tree II

发表于 |

给定一个最大树的根节点：最大树是指每个节点的值都大于该节点子树中的任何一个值。

这个最大树是由一个列表A生成的，生成规则如下：

  1. 如果A为空，return null
  2. 否则，找到A中最大的元素A[i]，生成值为A[i]的节点作为根节点
  3. 根节点的左孩子将由A[:i]生成
  4. 根节点的右孩子将由A[i+1:]生成
  5. 返回根节点

现在给定一个已经根据上述规则构造好的树的根节点root，原始列表为A。
现在向A末尾添加一个元素val，新数组定义为B，请你返回由数组B按照上述规则构造的树。

题意分析：
根据题目所说构造树的方式，也就是最大值为根节点，最大值左边的数组为左子树，右边的数组为右子树，很容易看出来如果将树还原成数组的话，应该是中序遍历

那么这里我们先将树还原成数组，然后将新加的值放进数组中，最后再将数组构造成树

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
29
30
31
class Solution(object):
    def insertIntoMaxTree(self, root, val):
        A = []
        def inorder(root):
            if root.left:
                inorder(root.left)
            A.append(root.val)
            if root.right:
                inorder(root.right)
        # 中序遍历获得原数组
        inorder(root)
        A.append(val)
        
        return self.transToTree(A)

    def transToTree(self, nums):
        # 递归方式构造树
        def construct(nums):
            if len(nums) == 1:
                node = TreeNode(nums[0])
                return node
            if not nums:
                return None
            maximum = max(nums)
            i = nums.index(maximum)
            root = TreeNode(maximum)
            root.left = construct(nums[:i])
            root.right = construct(nums[i+1:])
            return root
        
        return construct(nums)