题解 Java DFS recurse| #在二叉树中找到两个节点的最近公共祖先 [P1]

用一个global var记录LCA，然后dfs返回subtree里一共找到几个target。
如果两个都找到了 skip之后所有的backtrack(这个解法关键在于要确保LAC只被set一次)
time O(n), space O(h), where h is height of tree. \

import java.util.*;

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

public class Solution {
    int LCA = -1;  // init no LCA
  
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
      dfs(root, o1, o2);
      return LCA;
    }
  
    // Return 2 if LCA, 1 if in path between LCA and o1/o2, 0 otherwise.
    private int dfs(TreeNode root, int o1, int o2) {
      // skip null or if LCA already found
      if (root == null || LCA != -1) return 0; 
      int l = dfs(root.left, o1, o2);
      int r = dfs(root.right, o1, o2);
      // skip if LCA found in subtree.
      if (LCA != -1) return 0;
      
      int m = (root.val == o1 || root.val == o2) ? 1 : 0;
      // 如果两个数都找到了 那么这个node就是LAC。
      if (m + l + r == 2) LCA = root.val; // root is LCA
      return m + l + r;
    }
}