Post order traversal 的应用

Binary tree 的 post-order 遍历很实用，其遍历顺序的特点决定了其 bottom-up 的返回顺序，每次子树处理完了在当前节点上汇总结果，可以解决很多 和 subtree, tree path 相关的问题，在多叉树的情况下，也很容易扩展到各类的 search 问题，比如 Android Unlock Patterns.

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】

首先从这个树的结构我们可以发现。。不把最后的 leaf node 看完之前我们是不能知道所有 list 大小信息的，比如这里最后突然出现了一个 1 ，而其他位置都没有比它小的，这条 path 就突然变的最小了。

• 自底向上的return顺序 -- Post order

• 子树计算完在当前节点汇总的计算 -- Merge Sort

想到这层就已经很显然了，代码过于 trivial ，时间紧张就不写了。

LCA of deepest leaf node

这题在 LCA 类问题里有，递归和迭代的都可以解，不过都是 two-pass 的。 Post-order 可以 one-pass.

白板写了一下，发现也挺 trivial ..

    static TreeNode curLCA = null;
    static int maxDepth = 0;

    private static int postOrder(TreeNode root, int depth){
        if(root == null) return 0;
        if(root.left == null && root.right == null){
            if(depth > maxDepth){
                curLCA = root;
                maxDepth = depth;
            }
            return depth;
        }

        int left = postOrder(root.left, depth + 1);
        int right = postOrder(root.right, depth + 1);

        if(left == right && left >= maxDepth){
            maxDepth = Math.max(left, maxDepth);
            curLCA = root;
        }

        return Math.max(left, right);
    }

    public static void main(String[] args) {
        /*
        TreeNode nodeA = new TreeNode('A');
        TreeNode nodeB = new TreeNode('B');
        TreeNode nodeC = new TreeNode('C');
        TreeNode nodeE = new TreeNode('E');
        TreeNode nodeF = new TreeNode('F');
        TreeNode nodeH = new TreeNode('H');
        TreeNode nodeG = new TreeNode('G');
        TreeNode nodeI = new TreeNode('I');
        TreeNode nodeZ = new TreeNode('Z');

        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeE;
        nodeB.right = nodeF;
        nodeF.left = nodeG;
        nodeF.right = nodeI;
        nodeC.right = nodeH;
        nodeH.right = nodeZ;
        */

        TreeNode nodeA = new TreeNode('A');
        TreeNode nodeB = new TreeNode('B');
        TreeNode nodeC = new TreeNode('C');
        TreeNode nodeD = new TreeNode('D');
        TreeNode nodeE = new TreeNode('E');

        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeC.left = nodeD;
        nodeC.right = nodeE;

        postOrder(nodeA, 0);

        System.out.println(curLCA.chr);
    }

Find largest subtree

见本章后面"子树结构"里面的原题。