|
| 1 | +#!/usr/bin/python3 |
| 2 | +""" |
| 3 | +We are given the root node of a maximum tree: a tree where every node has a |
| 4 | +value greater than any other value in its subtree. |
| 5 | +
|
| 6 | +Just as in the previous problem, the given tree was constructed from an list A |
| 7 | +(root = Construct(A)) recursively with the following Construct(A) routine: |
| 8 | +
|
| 9 | +If A is empty, return null. |
| 10 | +Otherwise, let A[i] be the largest element of A. Create a root node with value |
| 11 | +A[i]. |
| 12 | +The left child of root will be Construct([A[0], A[1], ..., A[i-1]]) |
| 13 | +The right child of root will be Construct([A[i+1], A[i+2], ..., |
| 14 | +A[A.length - 1]]) |
| 15 | +Return root. |
| 16 | +Note that we were not given A directly, only a root node root = Construct(A). |
| 17 | +
|
| 18 | +Suppose B is a copy of A with the value val appended to it. It is guaranteed |
| 19 | +that B has unique values. |
| 20 | +
|
| 21 | +Return Construct(B). |
| 22 | +
|
| 23 | +Example 1: |
| 24 | +Input: root = [4,1,3,null,null,2], val = 5 |
| 25 | +Output: [5,4,null,1,3,null,null,2] |
| 26 | +Explanation: A = [1,4,2,3], B = [1,4,2,3,5] |
| 27 | +
|
| 28 | +Example 2: |
| 29 | +Input: root = [5,2,4,null,1], val = 3 |
| 30 | +Output: [5,2,4,null,1,null,3] |
| 31 | +Explanation: A = [2,1,5,4], B = [2,1,5,4,3] |
| 32 | +
|
| 33 | +Example 3: |
| 34 | +Input: root = [5,2,3,null,1], val = 4 |
| 35 | +Output: [5,2,4,null,1,3] |
| 36 | +Explanation: A = [2,1,5,3], B = [2,1,5,3,4] |
| 37 | +""" |
| 38 | + |
| 39 | + |
| 40 | +# Definition for a binary tree node. |
| 41 | +classTreeNode: |
| 42 | +def__init__(self,x): |
| 43 | +self.val=x |
| 44 | +self.left=None |
| 45 | +self.right=None |
| 46 | + |
| 47 | + |
| 48 | +classSolution: |
| 49 | +definsertIntoMaxTree(self,root:TreeNode,val:int)->TreeNode: |
| 50 | +""" |
| 51 | + Suppose B is a copy of A with the value val appended to it. |
| 52 | + val is ALWAYS on the right |
| 53 | +
|
| 54 | + insert the node in the root |
| 55 | + Go through the example one by one. |
| 56 | + Need to maintain the parent relationship -> return the sub-root |
| 57 | + """ |
| 58 | +ifnotroot: |
| 59 | +returnTreeNode(val) |
| 60 | + |
| 61 | +ifval>root.val: |
| 62 | +node=TreeNode(val) |
| 63 | +node.left=root |
| 64 | +returnnode |
| 65 | + |
| 66 | +root.right=self.insertIntoMaxTree(root.right,val) |
| 67 | +returnroot |