南昌网站建设服务百度网站域名
做不来，我做中等题基本上都是没有思路，这里需要先遍历祖先节点，那必然用先序遍历，这题还是官方题解容易理解，第二火的题解反而把我弄得脑袋昏昏的。
class Solution {
TreeNode ans;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root,p,q);
return ans;
}
boolean dfs(TreeNode root,TreeNode p, TreeNode q){
// 判断该树有没有p或q节点，有则为true
if(root==null) return false;
boolean l=dfs(root.left,p,q);
boolean r=dfs(root.right,p,q);
if((root==p||root==q)&&l==false&&r==false){
// 注意要有l==false&&r==false，防止遇到p或q直接退出函数，还要看其子树还有没有p或q。
return true;
}
if((root==p||root==q)&&(l==true||r==true)){
ans=root;
return true;
}else if((l==true&&r==true)){
ans=root;
return true;
}else {
return l||r;
}
}
}