找寻二叉树中两个节点的公共父节点中最近的那个节点
情况1. 节点只有left/right,没有parent指针,root已知
情况2. root未知,但是每个节点都有parent指针
情况3. 二叉树是个二叉查找树,且root和两个节点的值(a, b)已知
--------------------------------------------------------------------------------
虽然情况一是第一个情况,但是看上去比较复杂,我们放到最后来说,先从第二个情况开始说。
10
/ \
6 14
/ \ / \
4 8 12 16
/ \
3 5
画一个二叉树来做例子。如果我们要找3和8这两个节点的公共父亲节点,我们的做法是首先找到3到根节点的路劲,然后找到8到根节点的路径。
10
// \
6 14
/ \ / \
4 8 12 16
/ \
3 5
3的路径用红色表示,8的用绿色表示,可以看到, 这里的问题实际上是另一个我们熟知的问题,有2个相交的单链表,找出它们的相交点!
只要把这个二叉树的图片倒过来看,或者把脖子倒过来看就知道了:)那个方法也是传统的求出linkedList A的长度lengthA, linkedList B的长度LengthB。然后让长的那个链表走过abs(lengthA-lengthB)步之后,齐头并进,就能解决了。
自己写了个代码,总觉得有些拖沓冗余,希望有缘人看到文章之后能帮我改写的更和谐一些。
还是原来这个图,情况三,如果是个二叉搜索树,而且root和a, b已知,我们这个case假设a,b=3,8。从知道根这个条件我们很自然联想到递归(当然不递归也可以)地往下找。关键是收敛条件,什么情况下可以判断出当然检查的这个节点是最近父亲节点呢?其实从这个例子已经可以看出一些端倪了,如果当前访问的节点比a,b来的都小,肯定不行。如果比a,b都大,也不行。那也就是说,这个节点只有在a<=node<=b的区间内才成立(我们假定a<b这里)。这样的问题,网上广为流传着类似的代码:
好,前面的问题都解决了,我们再回过头来看第一个情况,只有ROOT和left, right节点,没有parent也不是排序树,怎么办?网络上也流传着很多所谓的LCA,RMQ算法,我们不暇找个最合适的,尤其是在面试的时候,特定时间空间下你很难写出一个逻辑非常复杂的东西(比如你会在面试的时候去实现一个Suffix Tree还是用动态规划来求最长公共子串,哪怕效率不同,我也选择动态规划:))。所以这里,碰到类似的问题的时候,我选择简单的记录找到node1和node2的路径,然后再把它们的路径用类似的情况二来做分析,比如还是node1=3,node2=8这个case.我们肯定可以从根节点开始找到3这个节点,同时记录下路径3,4,6,10,类似的我们也可以找到8,6,10。我们把这样的信息存储到两个vector里面,把长的vector开始的多余节点3扔掉,从相同剩余长度开始比较,4!=8, 6==6, coooool,我们找到了我们的答案。下面的代码完全按照这个思路写成
这段代码经历了大概30分钟的修改和debug,然后才逐渐稳定下来,真的很难想象如果是在面试的环境下,在纸笔之上会有如何的表现,可能真是只有天知道了。
分享到:
相关推荐
农行面试题zz.pdf
base zz zz zz zz zz base zz zz zz zz zz base zz zz zz zz zz base zz zz zz zz zz
微软面试题 测试篇ZZ shury 发表于 2004-12-5 12:14:00 以下测试题只有5分钟,如超过5分钟就放弃,因为超过了不会被微软录用的。 test 1 烧一根不均匀的绳需用一个小时,如何用它来判断半个小时? 折起来...
题库摩拜面试题合集题库摩拜面试题合集提取方式是百度网盘分享地址
题库广联达面试题合集题库广联达面试题合集提取方式是百度网盘分享地址
c语言面试题大汇总,来自中国源码zz,发表时间:2006.6.23 题后附简略答案。
C语言第8章_zz指针 详细的讲解了指针 这一节
](最新2021年面试题,高级面试题及附答案解析.md#1终止进程用什么命令-带什么参数) **答案:** kill [-s <信息名称或编号>][程序] 或 kill [-l <信息编号>] kill-9 pid ### [2、8.迷路,我的当前位置在哪?]...
sql,3SQL经典面试题
java面试笔试题 选择题 问答题 带答案 300题+ 面试必须掌握的知识
现代通信原理考试试题zz现代通信原理考试试题zz
CSP-J 第1套初赛模拟试题zz模拟题附答案
大厂面试真题北京-百度-Java中级提取方式是百度网盘分享地址
题库搜狗笔试面试题合集提取方式是百度网盘分享地址
200多个C#面试题含答案总共30页已编辑好可打印
题库完美世界笔试面试题合集提取方式是百度网盘分享地址
题库各大银行笔试面试题合集提取方式是百度网盘分享地址
题库Google校园招聘笔试面试题合集提取方式是百度网盘分享地址
今天将为大家总结MySQL中场景的面试题。围绕索引、事务、锁等几个方面的热点问题,系统化的总结。 资源内容包含: 1.史上最详细的一线大厂Mysql面试题详解 2.强烈推荐MySQL面试题和答案(仅供参考) 3.MySQL面试题...
作者针对50家企业笔试题做的精心整理;包括大量笔试真题及答案;其中包括巨人网络java笔试基础题分享 3 百度笔试题 7 百度2010校招运维部门笔试 8 百度2010年校园招聘软件...微软的面试题及答案-超变态但是很经典 89