class Solution(object):
def constructMaximumBinaryTree(self, nums):
n = len(nums)
if n == 0:
return None
st = []
for i in xrange(n):
val = nums[i]
newNode = TreeNode(val)
node = None
while len(st) > 0 and val > st[1].val:
node = st.pop()
newNode.left = node
if len(st) > 0:
st[1].right = newNode
st.append(newNode)
return st[0]
Sim Kieu
@simkieu
Posts made by simkieu

My O(n) time O(n) space solution in Python using a stack

Short Python recursive solution
helper method returns a pair of 2 values: the longest path in a subtree and its height.
class Solution(object): def helper(self, root): if not root: return 0, 1 pl, hl = self.helper(root.left) pr, hr = self.helper(root.right) return max(pl, pr, hl + hr + 2), max(hl, hr) + 1 def diameterOfBinaryTree(self, root): return self.helper(root)[0]

RE: Python DP O(n) space O(n^2) time
@jedihy the O(n) space, just incredible!

RE: Divide and Conquer, No radix/bucket sort, just run each bit, O(n) time
@ZephyrSails Thanks, I came up with the solution myself without looking up anything. I hope it does lol.

Straightforward and easytounderstand Python solution
class Solution(object): def licenseKeyFormatting(self, S, K): r = '' n = len(S) count = 0 for i in range(n1, 1, 1): if S[i] != '': r = S[i].upper() + r count += 1 if count == K: r = '' + r count = 0 if len(r) == 0 or r[0] != '': return r return r[1:len(r)]

Straightforward Python solution
class Solution(object): def magicalString(self, n): if n < 2: return n count = 1 a = [1]*n a[1] = 2 i, j = 1, 1 while j < n: for k in range(min(a[i], nj)): if a[j1] == 1: a[j+k] = 2 else: a[j+k] = 1 if a[j] == 1: count += min(a[i], nj) j += a[i] i += 1 return count

RE: Python solution
@skywalker_tju : I think because Python is much slower than Java. You can try to replace 'range' with 'xrange' and see if it helps.

Python solution using Preorder Traversal and 1 Upperbound
Serialize using Preorder Traversal, then Deserialize by doing this:

If the next element is smaller than the previous one we just saw, then this current one must be on the left of the previous node.

If the next element is greater than the previous node, we know it should be on the right side of some node, but we have not known which node yet:
2a/ If the next element has smaller value than the current upperbound, we can just insert it to the right of the previous node.
2b/ If the next element has greater value than the current upperbound, then we use the stack of upperbounds we've stored so far to pop elements out of the stack until we find the correct node to insert.
class Codec: def serialize(self, root): s = '' st = [] if root != None: st.append(root) while st: node = st.pop() s += str(node.val) + ',' if node.right: st.append(node.right) if node.left: st.append(node.left) if len(s) == 0: return s return s[0:len(s)1] def deserialize(self, data): l = data.split(',') if l[0] == '': return None st = [] root = TreeNode(int(l[0])) prev = root upperBound = sys.maxint for i in range(1, len(l)): if int(l[i]) < prev.val: prev.left = TreeNode(int(l[i])) upperBound = prev.val st.append(prev) prev = prev.left elif int(l[i]) < upperBound: prev.right = TreeNode(int(l[i])) prev = prev.right else: while len(st) > 0 and int(l[i]) > st[1].val: prev = st.pop() prev.right = TreeNode(int(l[i])) prev = prev.right if len(st) > 0: upperBound = st[1].val else: upperBound = sys.maxint return root
*Note: remember to update the upperbound and have a stack to store the upperbounds.


Intuitive Python solution
Starting from the 1st bit from left to right, we try to see if we can separate the numbers into 2 groups with bit 1 and bit 0. If they all have bit 0 or bit 0, we ignore that bit. If we can divide them into 2 non empty groups of bit 0 and bit 1, we want to hook one number from group bit 0 with 1 number from group bit 1, right?
Then what we want to do next for the next bit? We want to divide group bit 0 from previous bit into 2 sub groups: previous bit is 0 and current bit is 0, which I called zz (zero zero), and the group: previous bit is 0 and current bit is 1, which I called zo (zero one). We do the same with the group bit 1 from previous bit, dividing this group into 2 subgroups: previous bit is 1 and current bit is 0, which I called oz (one zero), and previous bit is 1 and current bit is 1, which I called oo (one one).
Now in order to get the maximum XOR of two numbers, I want to hook zz with oo, and zo with oz, thus creating a new groups of 2: [zz, oo] and [zo, oz]. For each group, we keep doing the same, hook one number from 1 array of the group to another element from the other array of the group.
The code is followed:
class Solution(object): def findMaximumXOR(self, nums): r = 0 l = [[nums, nums]] for i in range(31, 1, 1): count = 0 newL = [] for pair in l: zz, zo = [], [] for zero in pair[0]: if (zero >> i) & 1 == 0: zz.append(zero) else: zo.append(zero) oz, oo = [], [] for one in pair[1]: if (one >> i) & 1 == 0: oz.append(one) else: oo.append(one) if len(zz) > 0 and len(oo) > 0: newL.append([zz, oo]) count += 1 if len(zo) > 0 and len(oz) > 0: newL.append([zo, oz]) count += 1 if count > 0: l = newL r += 1 << i return r