這道題有好幾種情況，每種情況有不同的解法

一. 這棵樹是滿二叉樹，且節(jié)點(diǎn)從左到右、從上到下按順序標(biāo)記為1,2,3,...

滿二叉樹的子節(jié)點(diǎn)與父節(jié)點(diǎn)之間的關(guān)系為root = child / 2
兩個(gè)節(jié)點(diǎn)a,b，哪個(gè)節(jié)點(diǎn)大就將其標(biāo)記 / 2，直到兩個(gè)節(jié)點(diǎn)標(biāo)記相同，就得到了最低公共祖先
牛客網(wǎng)鏈接

public class LCA {
    public int getLCA(int a, int b) {
        if(a < 1 || b < 1) return -1;
        while(a != b){
            if(a < b){
                b /= 2;
            }else{
                a /= 2;
            }
        }
        return a;
    }
}

二. 這是一顆二叉搜索樹

leetcode鏈接
根據(jù)二叉搜索樹的性質(zhì)，共同祖先節(jié)點(diǎn)要么是兩個(gè)節(jié)點(diǎn)之一，要么是值在二者之間，根據(jù)這一性質(zhì)從根節(jié)點(diǎn)開始掃描

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(p == null) return q;
        if(q == null) return p;
        while(root != p && root != q){
            if(root.val > p.val && root.val > q.val){
                root = root.left;
            }else if(root.val < p.val && root.val < q.val){
                root = root.right;
            }else{
                return root;
            }
        }
        return root;
    }
}

三. 這是一顆普通的二叉樹

leetcode鏈接
這種情況下有兩種方案：

1. 采用遞歸先序遍歷的方法，分別從左右子樹中找目標(biāo)節(jié)點(diǎn)，如果左子樹中找到了二者，則返回左子樹，如果右子樹找到了二者則返回右子樹；左右子樹各找到一個(gè)，則返回當(dāng)前節(jié)點(diǎn)。
2. 先序遍歷記錄兩個(gè)節(jié)點(diǎn)的路徑，再比較路徑找到最低共同祖先，這種方法是劍指offer上的方法，但是實(shí)現(xiàn)起來比較復(fù)雜，實(shí)現(xiàn)后測(cè)試效果反而不如1的好。

經(jīng)實(shí)現(xiàn)比較，方法1的效率更高，這里給出方法1的代碼

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q)  return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null)   return root;
        return left != null ? left : right;
    }
}

四. 除root節(jié)點(diǎn)外，其余節(jié)點(diǎn)都有指向父節(jié)點(diǎn)的指針

這個(gè)就容易很多了，直接將兩個(gè)目標(biāo)節(jié)點(diǎn)通過指向父節(jié)點(diǎn)的指針一直找到root，記錄下路徑，再反向找到這兩個(gè)路徑要分叉的結(jié)點(diǎn)就是最低公共祖先。

五. 這是一顆普通的樹，非二叉

跟三的做法是一樣的，DLRRRRR