【编程题目】二叉树两个结点的最低共同父结点

时间:2022-12-14 23:02:52

75.二叉树两个结点的最低共同父结点(树)
题目:二叉树的结点定义如下:
struct TreeNode
{
int m_nvalue;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
输入二叉树中的两个结点,输出这两个结点在数中最低的共同父结点。

 

思路:修改后序遍历 我的方法需要一个额外的整数n来标定。

开始想用非递归,结果写不出来... 只好用递归了....

/*
75.二叉树两个结点的最低共同父结点(树)
题目:二叉树的结点定义如下:
struct TreeNode
{
int m_nvalue;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
输入二叉树中的两个结点,输出这两个结点在数中最低的共同父结点。
*/

//思路:修改后序遍历

#include
<iostream>
#include
<stdlib.h>
#include
<vector>
using namespace std;

typedef
struct TreeNode
{
int m_nvalue;
TreeNode
* m_pLeft;
TreeNode
* m_pRight;
}TreeNode;

void createTree(TreeNode * &T)
{
int data;
if(scanf("%d",&data) != 0 && data != 0)
{
T
= (TreeNode *)malloc(sizeof(TreeNode));
T
->m_nvalue = data;
T
->m_pLeft = NULL;
T
->m_pRight = NULL;
createTree(T
->m_pLeft);
createTree(T
->m_pRight);
}
return;
}



TreeNode
* findLowestCoParent(TreeNode * T, int N1, int N2, int * n)
{

if(T == NULL)
{
return NULL;
}
else
{
int a = 0;
int b = 0;
TreeNode
*A = findLowestCoParent(T->m_pLeft, N1, N2, &a);
TreeNode
*B = findLowestCoParent(T->m_pRight, N1, N2, &b);
if(T->m_nvalue == N1 || T->m_nvalue == N2)
{
(
*n)++;
}
(
*n) += (a + b);
if(a == 2)
{
return A;
}
if(b == 2)
{
return B;
}
if((*n) == 2)
{
return T;
}
}
}

int main()
{
TreeNode
* T = NULL;
createTree(T);
int n = 0;
TreeNode
* ans = findLowestCoParent(T, 8,6, &n);

printf(
"%d", ans->m_nvalue);
return 0;
}

 

找了找网上的答案,具体思路差不多,但是不需要额外的整数。 不过这类代码默认的是输入的两个结点一定有公共父节点,即输入的数字没有错。我的代码在输入出错的情况下如 root, 2000000会返回NULL, 而这类代码会返回root

来源:http://www.cnblogs.com/venow/archive/2012/08/31/2664969.html

#include "stdafx.h"
#include
<iostream>
#include
<fstream>
#include
<ctime>
using namespace std;

struct TreeNode
{
int m_nValue;
TreeNode
*m_pLeft;
TreeNode
*m_pRight;
};

//假定所创建的二叉树如下图所示
/*

/ \
3
/ \ /
3 6
/ \ \ / \
8 9 10 11
/ \
13
/
*/
void CreateBitree(TreeNode *&pNode, fstream &fin, TreeNode *&pNodeOne, TreeNode *&PNodeTwo)
{
int dat;
fin
>>dat;
if(dat == 0)
{
pNode
= NULL;
}
else
{
pNode
= new TreeNode();
pNode
->m_nValue = dat;
if (NULL == pNodeOne && !(rand() % 3))
{
pNodeOne
= pNode;
}
if (NULL == PNodeTwo && !(rand() % 5))
{
PNodeTwo
= pNode;
}
CreateBitree(pNode
->m_pLeft, fin, pNodeOne, PNodeTwo);
CreateBitree(pNode
->m_pRight, fin, pNodeOne, PNodeTwo);
}
}

//寻找二叉树两个结点的最低共同父节点
TreeNode *FindFirstCommonParentNode(TreeNode *pRoot, TreeNode *pNodeOne, TreeNode *pNodeTwo)
{
if (NULL == pRoot)
{
return NULL;
}
if (pRoot == pNodeOne || pRoot == pNodeTwo)
{
return pRoot;
}
TreeNode
*pLeft = FindFirstCommonParentNode(pRoot->m_pLeft, pNodeOne, pNodeTwo);
TreeNode
*pRight = FindFirstCommonParentNode(pRoot->m_pRight, pNodeOne, pNodeTwo);

if (NULL == pLeft) //1、左子树没有找到任何一个结点,则第一个公共父节点必定在右子树,而且找到第一个结点就是最低共同父节点
{
return pRight;
}
else if (NULL == pRight) //2、右子树没有找到任何一个结点,则第一个公共父节点必定在左子树,而且找到第一个结点就是最低共同父节点
{
return pLeft;
}
else //3、分别在结点的左右子树找到,则此节点必为第一个公共父节点
{
return pRoot;
}
}

int _tmain(int argc, _TCHAR* argv[])
{
srand((unsigned)time(NULL));
fstream fin(
"tree.txt");
TreeNode
*pRoot = NULL;
TreeNode
*pNodeOne = NULL;
TreeNode
*pNodeTwo = NULL;
TreeNode
*pParent = NULL;
CreateBitree(pRoot, fin, pNodeOne, pNodeTwo);
pParent
= FindFirstCommonParentNode(pRoot, pNodeOne, pNodeTwo);

cout
<<"第一个结点为:"<<pNodeOne->m_nValue<<endl;
cout
<<"第二个结点为:"<<pNodeTwo->m_nValue<<endl;
cout
<<"首个父结点为:"<<pParent->m_nValue<<endl;

cout
<<endl;
return 0;
}