236. Lowest Common Ancestor of a Binary Tree-（二叉树中两结点的最近公共祖先）
题目描述：
和235所不同的是，235指出二叉树是一棵特殊的树（二叉搜索树），而在本题中的二叉树是一棵普通的二叉树。
思路1：自顶向下的方法（时间复杂度o(n平方））
判断当前结点的左右子树是否包含这两个结点。
①如果左子树包含这两个结点，则最近公共祖先结点一定在左子树中。②如果右子树包含这2个个节点，则最近公共节点也一定在右子树中。③如果一个节点在左子树中，另一个节点在右子树中，则当前结点就是它们的最近公共祖先结点。
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(hasNode(root.left,p)&&hasNode(root.left,q)){
return lowestCommonAncestor(root.left,p,q);//p,q都在左子树
}
if(hasNode(root.right,p)&&hasNode(root.right,q)){
return lowestCommonAncestor(root.right,p,q);//p,q都在右子树
}
return root;//一个在左子树，一个在右子树
}
private boolean hasNode(TreeNode root,TreeNode node){
if(root==null){
return false;
}
if(root==node){
return true;
}
return hasNode(root.left,node)||hasNode(root.right,node);
}
}我们判断以一个结点为根的树是否含有某个结点时，需要遍历树的每个结点。接下来我们判断左子结点或者右结点为根的树中是否含有要找结点，仍然需要遍历。第二次遍历的操作其实在前面的第一次遍历都做过了。由于存在重复的遍历，本方法在时间效率上肯定不是最好的。
自顶向下的方法用了829ms，是真的慢！！！！！！！
思路2：自底向上的方法（时间复杂度o(n)）
自顶向下的方法需要重复遍历结点，自底向上的方法可以避免这种情况。
自底向上遍历结点，一旦遇到结点等于p或者q，则将其向上传递给它的父结点。父结点会判断它的左右子树是否都包含其中一个结点，如果是，则父结点一定是两个结点p,q的LCA，传递父结点到root。如果不是，我们向上传递其中的包含结点p或者结点q的子结点，或者null（如果子结点不包含任何一个）。该方法的时间复杂度为o(n).
递归实现：
* 以根节点为起点，往左右分支寻找，如果找到了p或q结点，则返回该节点。
* 否则，继续往叶子节点寻找。如果一直递归到null还是找不到该节点，则说明此分支上不存在该节点。
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null||root==p||root==q){
return root;
}
TreeNode LeftNode=lowestCommonAncestor(root.left,p,q);
TreeNode RightNode=lowestCommonAncestor(root.right,p,q);
if(LeftNode!=null&&RightNode!=null){
return root;//p,q分布在root两侧，返回即可
}else{
return (LeftNode!=null?LeftNode:RightNode);
}
}
}思路3：
参考博客：
https://blog.****.net/happyaaaaaaaaaaa/article/details/51635658