The main idea is as follows:
- Sort the array with
hdescending and if the height equal sorted with
- Building the binary tree as following rules:
2.1 using the first sorted people as root
2.2 iterate insert the people.
kof current people less than the root, insert the people in the left node, and increase the root with 1. It means that how many people preceding the root when doing inorder travel.
Otherwise, insert the node to the right. At the same time, you need to decrease the node
k-root.valwhich means the preceding already has k in the left subtree.
- Inorder travel the tree to get the final result.
NOTE: For the sort, why we should sort the value with same height in ascending? if not, the node with same height can't order correctly. It's possible that the node with less
k(height count) could be preceding the node with more
(5,3), (5,2). The
(5,3) could be preceding
class Node(object): def __init__(self,p): """ For general programming, it's better to create Person class. """ self.person=p self.hcnt=1 self.left=None self.right=None class Solution(object): def reconstructQueue(self,people): if not people: return  # sort the people with height descending # if height equal sort with hcnt ascending people.sort(cmp=lambda x,y:y-x if x!=y else x-y) root=Node(people) for p in people[1:]: self.insert(root,p,p) res= self.inorder(root,res) return res def insert(self,root,p,hcnt): # compare the height cnt with root # if the hight count less than the root, go to the left if hcnt<root.hcnt: if not root.left: root.left=Node(p) else: self.insert(root.left,p,hcnt) # increase the root cnt,means number preceding in the left subtree root.hcnt+=1 else: if not root.right: root.right=Node(p) else: # decrease the hcnt since it already has root.cnt before the left subtree self.insert(root.right,p,hcnt-root.hcnt) def inorder(self,root,res): if not root: return self.inorder(root.left,res) res.append(root.person) self.inorder(root.right,res)