百度面试题c。zz

找寻二叉树中两个节点的公共父节点中最近的那个节点

 

情况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，然后才逐渐稳定下来，真的很难想象如果是在面试的环境下，在纸笔之上会有如何的表现，可能真是只有天知道了。