236.二叉树的最近公共祖先

• 非递归套路做法

  • 一个map，key是节点，value是节点的父节点， 遍历一遍树，把map生成好，然后把a往上的全部节点加到一个set里去，然后从b开始往上串，每一次都去set里查有木有一样的，第一次遇到一样的就是最低公共祖先

• 递归套路做法

  • 如何分类？
  • x代表以x为头的树
    • 1） O1, O2 无一个在x上
    • 2） O1，O2 只一个在x上
    • 3） O1, O2 都在x为头的树上
      • ① 左右各一个
      • ②左 O1, O2
      • ③右 O1, O2
      • ④X是O1 ,

        - 左O2 || 右O2

        • X是O2
          • 左O1 || 右O1
    • 别看上图情况很多种，最后整合下来可以变成3种
      • 
  • info

ans -> o1,o2最初的交汇点是谁

  - findO1，  findO2  在这棵子树上有木有发现过O1  O2

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    public static TreeNode lowestCommonAncestor(TreeNode head, TreeNode o1, TreeNode o2) {
        return process(head, o1, o2).ans;
    }

    public static class Info {
        public TreeNode ans;
        public boolean findO1;
        public boolean findO2;

        public Info(TreeNode a, boolean f1, boolean f2) {
            ans = a;
            findO1 = f1;
            findO2 = f2;
        }
    }

    public static Info process(TreeNode X, TreeNode o1, TreeNode o2) {
        if (X == null) {
            return new Info(null, false, false);
        }
        Info leftInfo = process(X.left, o1, o2);
        Info rightInfo = process(X.right, o1, o2);
        boolean findO1 = X == o1 || leftInfo.findO1 || rightInfo.findO1;
        boolean findO2 = X == o2 || leftInfo.findO2 || rightInfo.findO2;
        TreeNode ans = null;
        if (leftInfo.ans != null) {
            ans = leftInfo.ans;
        }
        if (rightInfo.ans != null) {
            ans = rightInfo.ans;
        }
        if (ans == null) {
            if (findO1 && findO2) {
                ans = X;
            }
        }
        return new Info(ans, findO1, findO2);
    }