博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
淘宝面试题:有一个一亿节点的树,现在已知两个点,找这两个点的共同的祖先。...
阅读量:6340 次
发布时间:2019-06-22

本文共 343 字,大约阅读时间需要 1 分钟。

如题。

分析:

假设这棵树的每个结点都有n的指针指向n棵子树,可能有的子树为空。

已知的两个结点的关系有两种情况:

一个结点是另一个结点的祖先,这种情况第一个结点是两个结点的共同祖先;

第三个结点是两个结点的共同祖先。

算法:

递归遍历每个结点,

如果当前结点是空结点,返回NULL,

如果当前结点等于两个结点中的一个,返回当前结点指针

递归遍历当前结点的所有子树,返回n个结点指针,

如果只有一个指针非NULL,说明两个结点都在那棵子树中,返回那棵子树的指针,

如果有两个指针非NULL,说明当前结点是这两个结点的共同祖先,返回当前结点指针。

转载于:https://www.cnblogs.com/iamzhaiwei/archive/2012/06/30/2689664.html

你可能感兴趣的文章
Unity的赛车游戏实现思路
查看>>
[Android UI] Shape详解 (GradientDrawable)
查看>>
边学边体验django--HttpRequest 对象
查看>>
18.3 redis 的安装
查看>>
jdbc 简单连接
查看>>
多态初步认识
查看>>
数组处理:118
查看>>
为什么要优先使用组合而不是继承 .
查看>>
【MySql】权限不足导致的无法连接到数据库以及权限的授予和撤销
查看>>
android实现gif图与文字混排
查看>>
安卓新标准出台_告别乱弹窗_你的手机真会省电么?
查看>>
hdu1384Intervals(差分约束)
查看>>
python 字符编码
查看>>
269D Maximum Waterfall
查看>>
C++11 多线程
查看>>
sed-加速你在Linux的文件编辑
查看>>
HttpServer发送数据到kafka
查看>>
phpcms站---去除域名绑定目录中的HTML
查看>>
2017-5-3 打印控件、MDI 窗体容器
查看>>
20155303 2016-2017-2 《Java程序设计》第九周学习总结
查看>>