题目:二叉树的结点定义如下:
struct TreeNode
{
int m_nvalue;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
输入二叉树中的两个结点,输出这两个结点在数中最低的共同父结点。
分析:求数中两个结点的最低共同结点是面试中经常出现的一个问题。这个问题至少有两个变种。
第一变种是二叉树是一种特殊的二叉树:查找二叉树。也就是树是排序过的,位于左子树上的结点都比父结点小,而位于右子树的结点都比父结点大。我们只需要从根结点开始和两个结点进行比较。如果当前结点的值比两个结点都大,则最低的共同父结点一定在当前结点的左子树中。如果当前结点的值比两个结点都小,则最低的共同父结点一定在当前结点的右子树中。
第二个变种是树不一定是二叉树,每个结点都有一个指针指向它的父结点。于是我们可以从任何一个结点出发,得到一个到达树根结点的单向链表。因此这个问题转换为两个单向链表的第一个公共结点。
这个题:
从根结点开始,判断以当前结点为根的树中左右子树是不是包含我们要找的两个结点。如果两个结点都出现在它的左子树中,那最低的共同父结点也出现在它的左子树中。如果两个结点都出现在它的右子树中,那最低的共同父结点也出现在它的右子树中。如果两个结点一个出现在左子树中,一个出现在右子树中,那当前的结点就是最低的共同父结点
代码写不出见这里:
http://zhedahht.blog.163.com/blog/static/25411174201081263815813/
如果结点中有一个指向父结点的指针,我们可以把问题转化为求两个链表的共同结点。现在我们可以想办法得到这个链表
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;
}
分享到:
相关推荐
面试题12:能否用两个栈实现一个队列的功能 10.5 二叉树 面试题13:建立一个二叉树 面试题14:计算一棵二叉树的深度 面试题15:在二元树中找出和为某一值的所有路径 第11章 排序 11.1 插入排序 面试题1:编码实现...
每日刷题计划,记录做过的题目,内容包含剑指offer、程序员面试金典(CTCI)、数据结构 下面标题括号内的为对应包名 剑指offer(offer) java实现 03二维数组中的查找 04替换空格 05从尾到头打印链表 06重建二叉树 07用...
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 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格式的,绝对清晰
高级进阶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
05_面试题强化_多态相关 06_父类指针的步长和子类指针的步长不一样 07_课堂答疑什么时候子类的步长和父类的步长一样 08_抽象类基本语法 09_抽象类在多继承中的应用 10_面向抽象类编程_计算程序员工资 11_中午课程...
1. C 语言中的指针和内存泄漏 ............................................................................................................. 5 2. C语言难点分析整理 ................................. 二叉树的...