二叉树-最近的公共祖先

已知二叉树,求二叉树中给定的两个节点的最近公共祖先。 最近公共祖先: 两节点v与w的最近公共祖先u,满足在树上最低(离根最 远),且v,w两个节点都是u的子孙。 LeetCode 236. Lowest Common Ancestor of a Binary Tree

思考与分析

1.两个节点的公共祖先一定在从根节点,至这两个节点的路径上。 2.由于求公共祖先中的最近公共祖先,那么即同时出现在这两条路 径上的离根节点最远的节点(或离两个最近)。 3.最终算法即:求p节点路径,q节点路径,两路径上最后一个相同 的节点。

从根节点到某节点路径(深度搜索) 1.从根节点遍历(搜索)至该节点,找到该节点后就结束搜索。 2.将遍历过程中遇到的节点按照顺序存储起来,这些节点即路径节点。 前序遍历(深度优先)

void preorder(TreeNode *node, TreeNode *search){
    if(!node){
        return;
    }
    if(node == search){
        
    }
    preorder(node->left,search);
    preorder(node->right,search);
}
求根节点至某节点路径
void preorder(TreeNode *node,TreeNode *search, std::vector<TreeNode*> &path,std::vector<TreeNode*> &result,int &finish)//node 正在遍历节点,search待搜索节点,path 遍历时节点路径栈,result 最终搜索到节点search的路径结果,finish 记录是否找到节点search的遍历,未找到时是0,找到为1{
    if(!node || finish){
    return;//当node为空或已找到search 节点直接返回,结束搜索
     }
    path.push_back(node);//先序遍历时,将节点压入path栈
    if(node == search){
        finish = 1;
        result = path;
    }
    preorder(node->left,search,path,result,finish);
    preorder(node->right,search,path,result,finish);
    path.pop_back();//结束遍历node时,将node节点弹出path栈

}

1.求出较短路径的长度n。 2.同时遍历p节点的路径与q节点的路径,遍历n个节点,最后一个相同节点,即最近 公共祖先。

class Solution{
public:
    TreeNode* lowestCommonAncestor(TreeNode * root, TreeNode *p ,TreeNode *q){
        std::vector<TreeNode*> path;申明遍历用的临时栈
        std::vector<TreeNode*> node_p_path;//储存P节点路径
        std::vector<TreeNode*>node_q_path;//储存q节点路径
        int finish = 0;//记录是否完成搜索
        preorder(root, p,path,node_p_path,finish);
        path.clear();//清空path,finish,计算q节点路径
        finish = 0;
        preorder(root, q, path,node_q_path,finish);
        int path_len = 0;
        if(node_p_path.size() < node_q_path.size()){
            path_len = node_p_path.size();
        }
        else{
            path_len = node_q_path.size();
        }
        TreeNode * result = 0;
        for (int i = 0; i < path_len; i++){
            if(node_p_path[i] = node_q_path[i]){
                result = node_p_path[i];
            }//最后相同的节点为最近公共节点
        }
        return result;
}
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏项勇

笔记26 | 总结Android的获取系统时间的几种方法

1975
来自专栏算法与数据结构

PTA 7-4 排座位(25 分)

7-4 排座位(25 分) 布置宴席最微妙的事情,就是给前来参宴的各位宾客安排座位。无论如何,总不能把两个死对头排到同一张宴会桌旁!这个艰巨任务现在就交给你,对...

2459
来自专栏WD学习记录

牛客网 二叉树的深度

输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

831
来自专栏趣学算法

数据结构 第13讲 三元组 (F、C、L/R) 序列创建二叉树

/* 输入三元组 (F、C、L/R) 序列输入一棵二叉树的诸边(其中 F 表示双亲结点的标识,C 表示孩子结点标识,L/R...

3123
来自专栏数据处理

236. Lowest Common Ancestor of a Binary Tree

2354
来自专栏Java后端技术栈

为什么MySQL数据库索引选择使用B+树?

在进一步分析为什么MySQL数据库索引选择使用B+树之前,我相信很多小伙伴对数据结构中的树还是有些许模糊的,因此我们由浅入深一步步探讨树的演进过程,在一步步引出...

3981
来自专栏数据结构与算法

Day2平衡树笔记

线段树不支持的操作:删除,插入 ---- 常见的平衡树 treap 慢||好写 sbt(大小平衡的树) 非常快 比较好写 ||功能不全 rbt 红黑树 特...

3266
来自专栏数据处理

236. Lowest Common Ancestor of a Binary Tree

1725
来自专栏技术小黑屋

Java性能调优之容器扩容问题

在Java和Android编程中,我们经常使用类似ArrayList,HashMap等这些容器。这些容器少则存储几条,多则上千甚至更多。作为性能调优的一部分,容...

1121
来自专栏尾尾部落

[剑指offer] 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

1381

扫码关注云+社区

领取腾讯云代金券