树中两个节点的最低共同祖先系列

这道题有好几种情况，每种情况有不同的解法

一. 这棵树是满二叉树，且节点从左到右、从上到下按顺序标记为1,2,3,...

满二叉树的子节点与父节点之间的关系为root = child / 2
两个节点a,b，哪个节点大就将其标记 / 2，直到两个节点标记相同，就得到了最低公共祖先
牛客网链接

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链接
根据二叉搜索树的性质，共同祖先节点要么是两个节点之一，要么是值在二者之间，根据这一性质从根节点开始扫描

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. 采用递归先序遍历的方法，分别从左右子树中找目标节点，如果左子树中找到了二者，则返回左子树，如果右子树找到了二者则返回右子树；左右子树各找到一个，则返回当前节点。
2. 先序遍历记录两个节点的路径，再比较路径找到最低共同祖先，这种方法是剑指offer上的方法，但是实现起来比较复杂，实现后测试效果反而不如1的好。

经实现比较，方法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节点外，其余节点都有指向父节点的指针

这个就容易很多了，直接将两个目标节点通过指向父节点的指针一直找到root，记录下路径，再反向找到这两个路径要分叉的结点就是最低公共祖先。

五. 这是一颗普通的树，非二叉

跟三的做法是一样的，DLRRRRR