二叉树两个结点的最低共同父结点

1、对于二叉搜索树，里边的元素都是排好序的，那么从根节点向下搜索，找到第一个节点p满足p->data > pt1->data 且 p->data < pt2->data（假定pt1->data < pt2->data）即是满足要求的公共父节点；

节点结构：

struct node{

int data;

node *left, *right;

};

2、对于有指向父节点指针的二叉树，那么通过回溯找到根节点并对遍历过的节点予以保存，找到第一个相同的即是公共父节点。如果元素互异，保存元素以作比对即可，否则保存指针（地址）做比对；

这种情况下，树的节点结构应为：

struct node{

int data;

node *left, *right, *parent;

};

3、对于既没有排序，也没有父指针的一般情况,可以多费一些空间，将此树当作完全二叉树存入数组，那么每一个根节点与子节点的索引关系应为（k, 2k, 2k+1）当我们遍历到待查父节点的元素时记录其索引，将其索引依次除2，直到1，即全树的根节点。对于两个树同样操作，我们就能找到对应的共同父节点了。需要注意的是，我们没有必要存储所有的树节点，只需存储到包含两个待查父节点的节点即可。

节点结构：

struct node{

int data;

node *left, *right;

};

 

75.二叉树两个结点的最低共同父结点
题目：二叉树的结点定义如下：
struct TreeNode
{
int m_nvalue;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
输入二叉树中的两个结点，输出这两个结点在数中最低的共同父结点。
分析：求数中两个结点的最低共同结点是面试中经常出现的一个问题。这个问题至少有两个
变种。
ANSWER
Have done this. Do it again for memory...
TreeNode* getLCA(TreeNode* root, TreeNode* X, TreeNode *Y) {
if (root == NULL) return NULL;
if (X == root || Y == root) return root;
TreeNode * left = getLCA(root->m_pLeft, X, Y);
TreeNode * right = getLCA(root->m_pRight, X, Y);
if (left == NULL) return right;
else if (right == NULL) return left;
else return root;
}