Thinking process - Divide and Conquer + result type

1. if left is 1 and right is 1, return root + 2
2. if left is 1 or right is 1 and root is A or B, return root + 2
3. if left is 1 or right is 1, return left or right
4. else return root + 0

Mistakes

Two special cases

1. {1}, 1, 1 => 1
2. {1,2,3}, 1, 3 => 1

class ResultType {
    public TreeNode node;
    public int num; // number of nodes found

    public ResultType(TreeNode node, int num) {
        this.node = node;
        this.num = num;
    }
}

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 TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
        ResultType result = dfsHelper(root, A, B);

        if (result.num == 1 && (A == B || A == root) ) {
            return result.node;
        }

        return result.num == 2 ? result.node : null;
    }

    private ResultType dfsHelper(TreeNode root, TreeNode A, TreeNode B) {
        if (root == null) {
            return new ResultType(root, 0);
        }

        ResultType result = new ResultType(root, 0);
        if (root == A || root == B) {
            result.num = 1;
        }

        ResultType leftResult = dfsHelper(root.left, A, B);
        if (leftResult.num == 2) return leftResult;
        ResultType rightResult = dfsHelper(root.right, A, B);
        if (rightResult.num == 2) return rightResult;

        if (leftResult.num == 1 && rightResult.num == 1) {
            result.num = 2;
        } else if (leftResult.num == 1) {
            if (result.num == 1) {
                result.num++;
            } else {
                return leftResult;
            }
        } else if (rightResult.num == 1) {
            if (result.num == 1) {
                result.num++;
            } else {
                return rightResult;
            }
        }

        return result;
    }
}

Thinking process - stack

public class Solution { 
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
        if (root == null) return null; 

        Stack<TreeNode> pAncestors = new Stack<TreeNode>(); 
        Stack<TreeNode> qAncestors = new Stack<TreeNode>(); 

        if (!getAncestors(root, p, pAncestors) || !getAncestors(root, q, qAncestors)) return null; 

        while (!pAncestors.isEmpty() && !qAncestors.isEmpty()) { 
            TreeNode pParent = pAncestors.pop(); 
            if (pParent == qAncestors.pop()) return pParent; 
        } 

        return (!pAncestors.isEmpty()) ? pAncestors.pop() : qAncestors.pop(); 
    } 

    public boolean getAncestors(TreeNode root, TreeNode node, Stack<TreeNode> stack){ 
        if (root == null) return false; 
        stack.push(root); 
        if (root == node) return true; 


        if(getAncestors(root.left, node, stack)) return true; 
        if(getAncestors(root.right, node, stack)) return true; 

        stack.pop(); 
        return false; 
    } 
}