题解 | #在二叉树中找到两个节点的最近公共祖先#

写个倍增LCA
二叉树倍增按照2的次幂来增加， 即1, 2, 4, 8... 首先我们先预处理出每个节点2^j级祖先 用f[i][j] 表示i节点的2^j级祖先
查询时从大向小跳，即按照8, 4, 2, 1来；
具体:先把两个节点提到同一高度，在统一开始跳。一直跳到父亲节点相同，即为最近公共祖先。

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int f[100000][30];
    int  dep[100000];
// 预处理每个节点k级祖先
    void dfs(TreeNode* rt, int fa)
    {
        int x = rt->val;
        dep[x] = dep[fa] + 1;
        f[x][0] = fa;
        for (int i = 1; i <= 20; i ++ )
            f[x][i] = f[f[x][i-1]][i-1];
        if (rt->left)
        {
            dfs(rt->left, x);
        }
        if (rt->right) dfs(rt->right, x);
    }

    int Lca(int x, int y)
    {
        if (dep[x] < dep[y])
            swap(x, y);
        for (int i = 20; i >= 0; i -- )
            if (dep[f[x][i]] >= dep[y])
                x = f[x][i];
        if (x == y) return x;
        for (int i = 20; i >= 0; i -- )
        {
            if (f[x][i] != f[y][i])
                x = f[x][i], y = f[y][i];
        }
        return f[x][0];
    }

    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        dfs(root, root->val);
        return Lca(o1, o2);
    }
};