后续遍历大法

因为，该节点要找到最近公共祖先，所以需要先确定两个要找结点的位置，找到之后再找祖先，那么这里就自然可以想到二叉树的后序遍历，最后得到的就是最近的公共祖先。

思路：后序遍历

1.如果当前结点就是要找的结点，那么把当前结点值返回；
2.如果当前结点不是要找的结点，那么返回-1；
3.如果当前结点的左子树和右子树中，有一个返回的值不是-1，说明他们之中找到了一个结点，那么此时就要判断当前结点的值是不是要找的值，如果是，说明当前结点就是最近公共祖先，直接返回当前结点值；否则继续向上回退找祖先。
4.以上的时间复杂度是O(N)，空间复杂度O(N)

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        return postTreeTravel(root, o1, o2);
    }
    
    public int postTreeTravel(TreeNode root, int o1, int o2){
        if(root == null){
            return -1;
        }
        int left = postTreeTravel(root.left, o1, o2);
        int right = postTreeTravel(root.right, o1, o2);
        if(left != -1 && right != -1){
            //说明当前结点是最近公共结点
            return root.val;
        }else if(left != -1 || right != -1){
            //例外情况：当前结点既是要找的结点，也是最近公共结点
            if(o1 == root.val || o2 == root.val){
                return root.val;
            }
            //当前结点是父族结点，但不是公共结点
            return left == -1 ? right : left;
        }
        if(o1 == root.val || o2 == root.val){
            //说明找到一个结点
            return root.val;
        }
        //说明当前结点不是要找的结点
        return -1;
    }
}