Lowest Common Ancestor III

//Definition of TreeNode:
 class TreeNode {
      public int val;
      public TreeNode left, right;
      public TreeNode(int val) {
          this.val = val;
          this.left = this.right = null;
      }
  }
 
public class Solution {
    /**
     * @param root The root of the binary tree.
     * @param A and B two nodes
     * @return: Return the LCA of the two nodes.
     */
     public static void main(String[] args){
         // creat nodes
         TreeNode node_4 = new TreeNode(4); // node of root
         TreeNode node_3 = new TreeNode(3);
         TreeNode node_7 = new TreeNode(7);
         TreeNode node_5 = new TreeNode(5);
         TreeNode node_6 = new TreeNode(6);
         
         // construct tree
         node_4.left = node_3;
         node_4.right = node_7;
         node_7.left = node_5;
         node_7.right = node_6;
         
         // test node_3 node_5 
         Solution s = new Solution();
         TreeNode res = s.lowestCommonAncestor3(node_4, node_3, node_5);
         System.out.println(res.val);

     }
    class ResultType{
        TreeNode node;
        boolean A_exit;
        boolean B_exit;
        public ResultType(TreeNode node, boolean A_exit, boolean B_exit){
            this.node = node;
            this.A_exit = A_exit;
            this.B_exit = B_exit;
        }
    }
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
        /**思路这题要注意A和B不一定都在子树里。
         * 用一个ResultType来记录A和B是否在子树里存在，以及LCA node。
         * 用分治法。
         * 1：如果A或B在root上，那么LCA就在root上。
         * 2：如果左子树和右子树都有LCA，那么也说明当前LCA在root上。
         * 3：如果只有左边有LCA，那么LCA就在左边。
         * 4：如果只有右边有LCA，那么LCA就在右边。
        //  * 最后递归结束以后，需要判断是否A和B都存在*/
        //定义出口，root为空，或者a,b都不存在时候，返回空
        ResultType result = helper(root, A, B);
        
        if(result.A_exit&&result.B_exit){
            return result.node;
        }
        return null;
    }
    private ResultType helper(TreeNode root, TreeNode A, TreeNode B){
        //如果A或B在root上，那么LCA就在root上
        if(root == null){
            return new ResultType(null, false, false);
        }
        //分治法，两个小弟分别处理左右子树
        ResultType left = helper( root.left, A, B);
        ResultType right = helper( root.right, A, B);
        
        //A,B存在的条件。
        boolean A_exit = left.A_exit || right.A_exit || A == root;
        boolean B_exit = left.B_exit || right.B_exit || B == root;
        
        //如果a，b都在root，证明LCA在root
        if(A == root || B == root){
            return new ResultType(root,A_exit,B_exit);
        }
        //如果左右子树都非空
        if(left.node !=null && right.node != null ){
            return new ResultType(root,A_exit,B_exit);
        }
        //如果只有左边有LCA，那么LCA就在左边
        if(left.node !=null){
            return new ResultType(left.node,A_exit,B_exit);
        }
        //如果只有右边有LCA，那么LCA就在右边
        if(right.node !=null){
            return new ResultType(right.node,A_exit,B_exit);
        }
        //最后递归结束以后，需要判断是否A和B都存在
        return new ResultType(null,A_exit,B_exit);
    }
}