Post order traversal 的应用
Binary tree 的 post-order 遍历很实用,其遍历顺序的特点决定了其 bottom-up 的返回顺序,每次子树处理完了在当前节点上汇总结果,可以解决很多 和 subtree, tree path 相关的问题,在多叉树的情况下,也很容易扩展到各类的 search 问题,比如 Android Unlock Patterns.
Lexicographical path
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】
首先从这个树的结构我们可以发现。。不把最后的 leaf node 看完之前我们是不能知道所有 list 大小信息的,比如这里最后突然出现了一个 1 ,而其他位置都没有比它小的,这条 path 就突然变的最小了。
自底向上的return顺序 -- Post order
子树计算完在当前节点汇总的计算 -- Merge Sort
想到这层就已经很显然了,代码过于 trivial ,时间紧张就不写了。
LCA of deepest leaf node
这题在 LCA 类问题里有,递归和迭代的都可以解,不过都是 two-pass 的。 Post-order 可以 one-pass.
白板写了一下,发现也挺 trivial ..
Find largest subtree
见本章后面"子树结构"里面的原题。
Last updated