# 1650. Lowest Common Ancestor of a Binary Tree III
###### tags: `Leetcode` `FaceBook` `Medium` `Tree` `LCA`
Link: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iii/
## 思路
### $O(N)$ $O(1)$
先计算这两个node到root的距离，然后让他们两个到root的距离变成一样的，然后往上一起traverse，直到找到同一个node
### $O(N)$ $O(N)$
自己想出来der
一直向上遍历p，如果p的child里面有q,就返回q
和 [236 Lowest Common Ancestor of a Binary Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/) 很像，还比他简单
## Code $O(N)$ $O(1)$

class Solution {
    public Node lowestCommonAncestor(Node p, Node q) {
        int h1 = computeHeight(p);
        int h2 = computeHeight(q);
        if(h1 > h2){
            for(int i = 0;i < h1-h2;i++){
                p = p.parent;
            }
        }
        else{
            for(int i = 0;i < h2-h1;i++){
                q = q.parent;
            }
        }
        while(p!=q && p!=null && q!=null){
            p = p.parent;
            q = q.parent;
        }
        return p;
    }
    public int computeHeight(Node p){
        Node curr = p;
        int h = 0;
        while(curr!=null){
            curr = curr.parent;
            h++;
        }
        return h;
    }
}

## Code $O(N)$ $O(N)$

class Solution {
    public Node lowestCommonAncestor(Node p, Node q) {
        while(p != null){
            if(findQ(p,q)){
                return p;
            }
            p = p.parent;
        }
        return null;
    }
    public boolean findQ(Node root, Node q){
        if(root == q) return true;
        if(root == null) return false;
        else{
            if(findQ(root.left,q)){
                return true;
            }
            else{
                return findQ(root.right,q);
            }
        }
    }
}