# 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**

![](/files/-MUt7b9ni_PD5R4gSI4P)

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

## LCA of deepest leaf node

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

![](/files/-MUt7b9pI21bxb4JUPEp)

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

```java
    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

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/binary_tree/post_order_traversal_de_ying_yong.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.