http://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116

/**
* 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);
}
};

2022-12-15 16:06

2022-12-31 14:41

2022-12-20 07:39

2022-12-26 23:50

2022-12-10 00:04

2022-12-16 02:48

2022-12-09 12:02