/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*///用f(x)表示x节点的子树是否包含p或者q//则满足公共祖先节点有两种情况组成//1.f(x.left) && f(x.right)//2.f(x.left) || f(x.right) && x==另一个
class Solution {TreeNode ans = new TreeNode();public boolean dfs(TreeNode root, TreeNode p, TreeNode q){if(root == null) return false;boolean lson = dfs(root.left, p, q);boolean rson = dfs(root.right, p, q);//情况1if(lson && rson){ans = root;}//情况2else if((lson || rson) && (root.val == q.val || root.val == p.val)){ans = root;}//因为所有结点的val都不相同，所以直接返回就行，不用考虑复杂情况return rson || lson || (root.val == p.val || root.val == q.val);}public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {dfs(root, p, q);return ans;}
}