题目:二叉树的结点定义如下:
struct TreeNode
{
int m_nvalue;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
输入二叉树中的两个结点,输出这两个结点在数中最低的共同父结点。
分析:求数中两个结点的最低共同结点是面试中经常出现的一个问题。这个问题至少有两个变种。
第一变种是二叉树是一种特殊的二叉树:查找二叉树。也就是树是排序过的,位于左子树上的结点都比父结点小,而位于右子树的结点都比父结点大。我们只需要从根结点开始和两个结点进行比较。如果当前结点的值比两个结点都大,则最低的共同父结点一定在当前结点的左子树中。如果当前结点的值比两个结点都小,则最低的共同父结点一定在当前结点的右子树中。
第二个变种是树不一定是二叉树,每个结点都有一个指针指向它的父结点。于是我们可以从任何一个结点出发,得到一个到达树根结点的单向链表。因此这个问题转换为求两个单向链表的第一个公共结点。
现在我们回到这个问题本身。所谓共同的父结点,就是两个结点都出现在这个结点的子树中。因此我们可以定义一函数,来判断一个结点的子树中是不是包含了另外一个结点。这不是件很难的事,我们可以用递归的方法来实现:
/*
// If the tree with head pHead has a node pNode, return true.
// Otherwise return false.
*/
bool HasNode(TreeNode* pHead, TreeNode* pNode)
{
if(pHead == pNode)
return true;
bool has = false;
if(pHead->m_pLeft != NULL)
has = HasNode(pHead->m_pLeft, pNode);
if(!has && pHead->m_pRight != NULL)
has = HasNode(pHead->m_pRight, pNode);
return has;
}
我们可以从根结点开始,判断以当前结点为根的树中左右子树是不是包含我们要找的两个结点。如果两个结点都出现在它的左子树中,那最低的共同父结点也出现在它的左子树中。如果两个结点都出现在它的右子树中,那最低的共同父结点也出现在它的右子树中。如果两个结点一个出现在左子树中,一个出现在右子树中,那当前的结点就是最低的共同父结点。基于这个思路,我们可以写出如下代码:
/*
// Find the last parent of pNode1 and pNode2 in a tree with head pHead
*/
TreeNode* LastCommonParent_1(TreeNode* pHead, TreeNode* pNode1, TreeNode* pNode2)
{
if(pHead == NULL || pNode1 == NULL || pNode2 == NULL)
return NULL;
// check whether left child has pNode1 and pNode2
bool leftHasNode1 = false;
bool leftHasNode2 = false;
if(pHead->m_pLeft != NULL)
{
leftHasNode1 = HasNode(pHead->m_pLeft, pNode1);
leftHasNode2 = HasNode(pHead->m_pLeft, pNode2);
}
if(leftHasNode1 && leftHasNode2)
{
if(pHead->m_pLeft == pNode1 || pHead->m_pLeft == pNode2)
return pHead;
return LastCommonParent_1(pHead->m_pLeft, pNode1, pNode2);
}
// check whether right child has pNode1 and pNode2
bool rightHasNode1 = false;
bool rightHasNode2 = false;
if(pHead->m_pRight != NULL)
{
if(!leftHasNode1)
rightHasNode1 = HasNode(pHead->m_pRight, pNode1);
if(!leftHasNode2)
rightHasNode2 = HasNode(pHead->m_pRight, pNode2);
}
if(rightHasNode1 && rightHasNode2)
{
if(pHead->m_pRight == pNode1 || pHead->m_pRight == pNode2)
return pHead;
return LastCommonParent_1(pHead->m_pRight, pNode1, pNode2);
}
if((leftHasNode1 && rightHasNode2) || (leftHasNode2 && rightHasNode1))
return pHead;
return NULL;
}
接着我们来分析一下这个方法的效率。函数HasNode的本质就是遍历一棵树,其时间复杂度是O(n)(n是树中结点的数目)。由于我们根结点开始,要对每个结点调用函数HasNode。因此总的时间复杂度是O(n^2)。
我们仔细分析上述代码,不难发现我们判断以一个结点为根的树是否含有某个结点时,需要遍历树的每个结点。接下来我们判断左子结点或者右结点为根的树中是否含有要找结点,仍然需要遍历。第二次遍历的操作其实在前面的第一次遍历都做过了。由于存在重复的遍历,本方法在时间效率上肯定不是最好的。
前面我们提过如果结点中有一个指向父结点的指针,我们可以把问题转化为求两个链表的共同结点。现在我们可以想办法得到这个链表。我们在这里稍作变化即可:
/*
// Get the path form pHead and pNode in a tree with head pHead
*/
bool GetNodePath(TreeNode* pHead, TreeNode* pNode, std::list<TreeNode*>& path)
{
if(pHead == pNode)
return true;
path.push_back(pHead);
bool found = false;
if(pHead->m_pLeft != NULL)
found = GetNodePath(pHead->m_pLeft, pNode, path);
if(!found && pHead->m_pRight)
found = GetNodePath(pHead->m_pRight, pNode, path);
if(!found)
path.pop_back();
return found;
}
由于这个路径是从跟结点开始的。最低的共同父结点就是路径中的最后一个共同结点:
/*
// Get the last common Node in two lists: path1 and path2
*/
TreeNode* LastCommonNode
(
const std::list<TreeNode*>& path1,
const std::list<TreeNode*>& path2
)
{
std::list<TreeNode*>::const_iterator iterator1 = path1.begin();
std::list<TreeNode*>::const_iterator iterator2 = path2.begin();
TreeNode* pLast = NULL;
while(iterator1 != path1.end() && iterator2 != path2.end())
{
if(*iterator1 == *iterator2)
pLast = *iterator1;
iterator1++;
iterator2++;
}
return pLast;
}
有了前面两个子函数之后,求两个结点的最低共同父结点就很容易了。我们先求出从根结点出发到两个结点的两条路径,再求出两条路径的最后一个共同结点。代码如下:
/*
// Find the last parent of pNode1 and pNode2 in a tree with head pHead
*/
TreeNode* LastCommonParent_2(TreeNode* pHead, TreeNode* pNode1, TreeNode* pNode2)
{
if(pHead == NULL || pNode1 == NULL || pNode2 == NULL)
return NULL;
std::list<TreeNode*> path1;
GetNodePath(pHead, pNode1, path1);
std::list<TreeNode*> path2;
GetNodePath(pHead, pNode2, path2);
return LastCommonNode(path1, path2);
}
这种思路的时间复杂度是O(n),时间效率要比第一种方法好很多。但同时我们也要注意到,这种思路需要两个链表来保存路径,空间效率比不上第一个方法。
分享到:
相关推荐
面试题12:能否用两个栈实现一个队列的功能 10.5 二叉树 面试题13:建立一个二叉树 面试题14:计算一棵二叉树的深度 面试题15:在二元树中找出和为某一值的所有路径 第11章 排序 11.1 插入排序 面试题1:编码实现...
浮点运算器可用两个松散连接的定点运算部件--阶码部件和尾数部件来实现 B.阶码部件可实现加、减、乘、除4种运算 C.阶码部件只可进行阶码相加、相减和相乘操作,而不能进行除操作 D.尾数部件只进行乘法和除...
如果对一棵有n个结点的完全二叉树的结点按层序编号则对任一结点i(1≤i≤n),有: ①如果i=1,则结点i无父结点,是二叉树的根;如果i>1,则父结点是ëi/2û; ② 如果2i>n,则结点i为叶子结点,无左子结点;否则,...
1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,多和面试官沟通,然后开始做一些整体的设计和规划。不要急于提交,自己测试几个用例避免错误...
leetcode 分类 nowcoder 每日刷题计划,记录做过的题目,内容包含剑指offer、程序员面试金典(CTCI)、数据结构 下面标题括号内的为对应包名 剑指offer(offer) java实现 ...37两个链表的第一个公共结点 38
试写出一个算法,将该线性单链表分解成两个线性单链表,其中一个链表中的结点值均为奇数,而另一个链表中的结点值均为偶数,且这两个链表均按值从小到大链接。 8. 已知二叉树的后序遍历和中序遍历序列,构造对应的...
1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char const*...84. C语言惠通面试题 428 85. C语言常用宏定义 450
目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
不多说了 直接上目录: 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 ...84. C语言惠通面试题 428 85. C语言常用宏定义 450 有需要的朋友可以根据需求下载,内容为WORD格式的,绝对清晰
1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
高级进阶c语言教程 目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
》主要定位于有一定C/C++语言编程基础、想通过学习算法与数据结构提升编程水平的读者,也可作为具有一定编程经验的程序员以及大中专院校学生学习数据结构和算法的参考书。 第1篇 算法基础篇 1 第1章 算法概述 2 ...
对于C++程序员的Java Java数据结构的类库 小结 问题 第2章 数组 Array专题Applet Java中数组的基础知识 将程序划分成类 类接口 Ordered专题applet 有序数组的Java代码 对数 存储对象 大O表示法 为什么...
对于C++程序员的Java Java数据结构的类库 小结 问题 第2章 数组 Array专题Applet Java中数组的基础知识 将程序划分成类 类接口 Ordered专题applet 有序数组的Java代码 对数 存储对象 大O表示法 为什么不用数组表示...
全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和队列、链表、递归、进阶排序、二叉树、红黑树、哈希表及图形等知识。附录中则提供了运行专题Applet和例程、相关书籍和问题解答。本书提供了学完一门编程...
因为小弟权限不够,所以分开两个帖子上存,资源名称分别是: Java数据结构和算法中文第二版(1) Java数据结构和算法中文第二版(2) 【内容简介】 本书可帮助读者: 通过由基于JAVA的演示所组成的可视专题讨论来掌握...
(1)复习并灵活掌握二叉树的各种存储结构和遍历方法, (2)了解静态链表,并掌握其构造方法。 (3)掌握哈夫曼树的构造过程和哈夫曼编码的求解方法 2.主要内容 (1)先统计某中文档中所有汉字的出现次数(GB码或UTF-8编码,...