本人最近的第一道leetcode算法题
想了好久都没做出来，有点思路但太混乱了
消化整理一下。主要也是参考了leetcode的官方解答
题目:
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
思路1.递归
比较容易想到的，是一种深度优先搜索的概念，但是从根部往下找，还是从叶子往上找呢？
这个题目要求找"最近的公共祖先"，那也就是说，从叶子网上找，能找到深度最大的结果，再往上一直到根，虽然也都是祖先，但不符合深度最大的要求了。
所以，先遍历到底，再开始找。
其次，如果用递归，怎样符合要求呢？
假设某个节点x, 只要满足两者任一
(1）x的左子树和x的右子树里面都有p或q节点
(2) x是p或者q, 同时左子树或者右子树有p或q节点
我们将“有”的这种结果，用布尔值来表示，然后返回节点x
用数学语言来表达，就是(&&
) || ((x==p||x==q)&&(
||
)),后面这个条件是必要的，因为p或者q为祖先的时候，必须保证另外一个节点在它的子树里，否则就不能构成公共祖先的前提了
#代码
```
class Solution {
private TreeNode ans;//用完有个变量作为出口返回值
public Solution() {
this.ans = null;
}
private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return false;
boolean lson = dfs(root.left, p, q);//先递归到左子树底，遇到空，会返回false
boolean rson = dfs(root.right, p, q);//再递归到右子树底，遇到空，会返回false
if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {//满足需要存储的情况
ans = root;//找到了 就存储 用不用有返回值，关系不大
}
return lson || rson || (root.val == p.val || root.val == q.val);//左或右子树里有节点，或者节点等于p或q 才返回true,否则都能返回false //不管是否找到，也要把是否存在节点的布尔值返回
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
this.dfs(root, p, q);//直接调用定义的方法就好了，不是说一定只能用它提供的方法的
return this.ans;//调用完就返回这个值，或者有值或者为null
}
}
```
##分析
时间复杂度：O(n),其中n是二叉树节点个数，因为最差情况是每个节点都遍历了一遍，在最后两个节点中找到
空间复杂度：O(n)，其中n是二叉树节点个数，每个节点都找一遍，最差情况下创建了n个boolean值的对象空间
个人认为最重要的是，要找到合适的载体来存储和返回这个值，另外题目给的方法就一定是递归的方法，给的方法的返回值类型，不一定就是递归的类型，完全可以自己定义一个
#思路二：存储父节点
###遍历每个节点，存储每个节点的父节点，然后如果p的节点和q有公共的父节点，那么这个父节点即为祖先
