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

• 子树计算完在当前节点汇总的计算 -- Collections.sort(new Comparator<ArrayList>)

public static ArrayList<ArrayList<Integer>> search (Node root){
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        if(root==null) return list;
        ArrayList<ArrayList<Integer>> left =search(root.left);
        ArrayList<ArrayList<Integer>> right = search(root.right);
        for(ArrayList<Integer> tmp : left ){
            tmp.add(root.value);
            list.add(tmp);
        }
        for(ArrayList<Integer> tmp : right){
            tmp.add(root.value);
            list.add(tmp);
        }
        if(left.size()==0 && right.size()==0){
            ArrayList<Integer> tmp = new ArrayList<Integer>();tmp.add(root.value);
            list.add(tmp);
        }
        Collections.sort(list, new Comparator<ArrayList<Integer>>(){

            @Override
            public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
                // TODO Auto-generated method stub
                int i =0;
                while(i<o1.size() && i<o1.size()){
                    if(o1.get(i)!=o2.get(i)) return o1.get(i).compareTo(o2.get(i));
                    i++;
                }
                if(i==o1.size() && i==o2.size()) return 0;
                if(i==o1.size()) return -1;
                else return 1;
            }

        });
        return list;
    }

LCA of deepest leaf node

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

这道题利用返回的深度信息, LCA一定是左右深度最深并且平衡的树节点, 所以check两个条件: 1. 是否平衡 2. 深度是否最深

    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);
    }