/*************************************************************************
题目:树中两个节点的最低公共祖先
*************************************************************************/
#include<stdio.h>
#include <list>
#include<vector>
using namespace std;
struct TreeNode
{
int m_nValue;
std::vector<TreeNode*> m_vChildren;
};
TreeNode* CreateTreeNode(int value)
{
TreeNode* pNode = new TreeNode();
pNode->m_nValue = value;
return pNode;
}
void ConnectTreeNodes(TreeNode* pParent, TreeNode* pChild)
{
if(pParent != NULL)
{
pParent->m_vChildren.push_back(pChild);
}
}
bool GetNodePath(TreeNode* pRoot, TreeNode* pNode, list<TreeNode*>& path)
{
if(pRoot == pNode)
return true;
path.push_back(pRoot);
bool found = false;
vector<TreeNode*>::iterator i = pRoot->m_vChildren.begin();
while(!found && i < pRoot->m_vChildren.end())
{
found = GetNodePath(*i, pNode, path);
++i;
}
if(!found)
path.pop_back();
return found;
}
TreeNode* GetLastCommonNode
(
const list<TreeNode*>& path1,
const list<TreeNode*>& path2
)
{
list<TreeNode*>::const_iterator iterator1 = path1.begin();
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;
}
TreeNode* GetLastCommonParent(TreeNode* pRoot, TreeNode* pNode1, TreeNode* pNode2)
{
if(pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
return NULL;
list<TreeNode*> path1;
GetNodePath(pRoot, pNode1, path1);
list<TreeNode*> path2;
GetNodePath(pRoot, pNode2, path2);
return GetLastCommonNode(path1, path2);
}
// ====================测试代码====================
void Test(char* testName, TreeNode* pRoot, TreeNode* pNode1, TreeNode* pNode2, TreeNode* pExpected)
{
if(testName != NULL)
printf("%s begins: \n", testName);
TreeNode* pResult = GetLastCommonParent(pRoot, pNode1, pNode2);
if((pExpected == NULL && pResult == NULL) ||
(pExpected != NULL && pResult != NULL && pResult->m_nValue == pExpected->m_nValue))
printf("Passed.\n");
else
printf("Failed.\n");
}
// 形状普通的树
// 1
// / \
// 2 3
// / \
// 4 5
// / \ / | \
// 6 7 8 9 10
void Test1()
{
TreeNode* pNode1 = CreateTreeNode(1);
TreeNode* pNode2 = CreateTreeNode(2);
TreeNode* pNode3 = CreateTreeNode(3);
TreeNode* pNode4 = CreateTreeNode(4);
TreeNode* pNode5 = CreateTreeNode(5);
TreeNode* pNode6 = CreateTreeNode(6);
TreeNode* pNode7 = CreateTreeNode(7);
TreeNode* pNode8 = CreateTreeNode(8);
TreeNode* pNode9 = CreateTreeNode(9);
TreeNode* pNode10 = CreateTreeNode(10);
ConnectTreeNodes(pNode1, pNode2);
ConnectTreeNodes(pNode1, pNode3);
ConnectTreeNodes(pNode2, pNode4);
ConnectTreeNodes(pNode2, pNode5);
ConnectTreeNodes(pNode4, pNode6);
ConnectTreeNodes(pNode4, pNode7);
ConnectTreeNodes(pNode5, pNode8);
ConnectTreeNodes(pNode5, pNode9);
ConnectTreeNodes(pNode5, pNode10);
Test("Test1", pNode1, pNode6, pNode8, pNode2);
}
// 树退化成一个链表
// 1
// /
// 2
// /
// 3
// /
// 4
// /
// 5
void Test2()
{
TreeNode* pNode1 = CreateTreeNode(1);
TreeNode* pNode2 = CreateTreeNode(2);
TreeNode* pNode3 = CreateTreeNode(3);
TreeNode* pNode4 = CreateTreeNode(4);
TreeNode* pNode5 = CreateTreeNode(5);
ConnectTreeNodes(pNode1, pNode2);
ConnectTreeNodes(pNode2, pNode3);
ConnectTreeNodes(pNode3, pNode4);
ConnectTreeNodes(pNode4, pNode5);
Test("Test2", pNode1, pNode5, pNode4, pNode3);
}
// 树退化成一个链表,一个结点不在树中
// 1
// /
// 2
// /
// 3
// /
// 4
// /
// 5
void Test3()
{
TreeNode* pNode1 = CreateTreeNode(1);
TreeNode* pNode2 = CreateTreeNode(2);
TreeNode* pNode3 = CreateTreeNode(3);
TreeNode* pNode4 = CreateTreeNode(4);
TreeNode* pNode5 = CreateTreeNode(5);
ConnectTreeNodes(pNode1, pNode2);
ConnectTreeNodes(pNode2, pNode3);
ConnectTreeNodes(pNode3, pNode4);
ConnectTreeNodes(pNode4, pNode5);
TreeNode* pNode6 = CreateTreeNode(6);
Test("Test3", pNode1, pNode5, pNode6, NULL);
}
// 输入NULL
void Test4()
{
Test("Test4", NULL, NULL, NULL, NULL);
}
int main()
{
Test1();
Test2();
Test3();
Test4();
return 0;
}
==参考剑指offer
分享到:
相关推荐
解题思路明确一点即可:自己解题* 二叉搜索树中两个节点的最低公共祖先public class Solution {* 获得二叉搜索树中两个节点的最低公共祖先pu
类似题目1.二叉搜索树解法:因为二叉搜索树 左孩子>父节点>右孩子,因此可以从跟遍历如果传入的两个节点都小于当前比较的节点,那么这两个节点的公共节点在当前比较节
因为树的结构不同所以需要分情况...当树为二叉排序树,寻找给定两节点的最低公共祖先 当树为普通树,每个节点中有指针指向其父节点 当树为二叉树,每个节点仅有左右孩子指针 当树为普通树,每个节点仅有左右孩子指针
在排序数组中查找数字.py 二叉搜索树的第k大节点.py 二叉树的深度.py 数组中数字出现的次数.py 和为s的数字.py 翻转字符串.py 队列的最大值.py n个骰子的点数.py ...树中两个节点的最低公共祖先.py
50.第一个只出现一次的字符 50.字符流中第一个不重复的字符 51.数组中的逆序对 Array 常考 52.两个链表的第一个公共结点 Linked List 53.数字在排序数组中出现的次数 ...68.树中两个节点的最低公共祖先 常考
50. 树中两个节点的最低公共祖先 51. 找出重复的数 52. 构建乘积数组 53. 正则表达式匹配 54. 表示数值的字符串 55. 字符流中第一个不重复的字符 56. 链表中环的入口节点 57. 删除链表中重复的节点 58. ...
//求二叉树的节点个数//前序打印叶子节点//二叉树的遍历//求二叉树的第k层节点的值//交换二叉树的左右子树//求二叉树中两个节点的最低公共祖先节点//求双亲节点//判断两棵二叉树是否相同//二叉树删除节点//二叉树...
二叉搜索树的最低公共祖先 树 简单的 二叉树路径 树 简单的 左叶总和 树 简单的 路径求和 III 树 简单的 二叉搜索树中的查找模式 树 简单的 BST 中的最小绝对差 树 简单的 将 BST 转换为更大的树 树 简单的 二叉树的...
最低公共祖先 BinarySearchTree.lowestAncestor() 汉明权重 1 位 三的幂给定一个整数,写一个函数来判断它是否是三的幂。 爬楼梯 您正在爬楼梯。 需要n步才能到达顶部。 二的幂给定一个整数,写一个函数来判断它是否...
树中两个节点的最低公共祖先 判断是否为平衡二叉树-解法二 机器人运动的范围 矩阵中的路径 滑动窗口最大值 数据流的中位数 删除链表中重复的节点[无序的情况下-HashSet] 二. Notes for Android Heros 三. Notes for ...
二叉搜索树的最低公共祖先-BST Property Easy 102.二叉树级别遍历-BFS Easy 100.Same树 字符串转整数(atoi)简单 最小堆栈容易 轻松计算素数 ---------------待完成------------------------最大 bst 子树 23
螺旋矩阵跳跃游戏合并间隔独特的路径设置矩阵零排序颜色子集词搜索解码方式二叉树中序遍历验证二叉搜索树二叉树级别顺序遍历二叉树之字形水平顺序遍历从前序和中序遍历构造二叉树在每个节点中填充下一个右指针字梯...