解开的都是套路: Facebook脸家 - Lexicographical path
Lexicographical path
5 / \ 3 2 / \ \ 2 4 4 \ 1
FB 面经,自底向上的 path 有【1,4,2,5】,【4,3,5】,【2,3,5】,要求按自底向上的 lexicographical order 返回排序的 path,比如在这里是 【1,4,2,5】, 【2,3,5】,【4,3,5】
Analysis: Post order, for each node keep left & right paths, merge 2 into one single path.
Complexity: O(nlgn), each node has at most lgn node in the path.
Read full article from 解开的都是套路: Facebook脸家 - Lexicographical path