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

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

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

写个倍增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);
    }
};

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-20 07:39
门头沟学院_2023
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
2022-12-16 02:48
门头沟学院_2022
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议