|
1. 二叉搜索树
给定一棵二叉搜索树(BST)，找出树中两个结点的最低公共祖先结点(LCA)。二叉搜索树结点定义：
struct node {
int data;
struct node* left;
struct node* right;
};
如下图为一棵BST，结点2和8的LCA是6，结点4和2的LCA是2。注意，与文章二叉树两结点的最低公共祖先结点 中不同，这里已经说明是二叉搜索树（BST），所以可以利用BST的性质进行处理更加简单。
_______6______
/ \
___2__ ___8__
/ \ / \
0 _4 7 9
/ \
3 5
有四种情况需要考虑，分别是
1）两个结点都在树的左边
2）两个结点都在树的右边
3）一个结点在树的左边，一个结点在树的右边
4）当前结点等于这两个结点中的一个
对于第1种情况，LCA一定在当前结点的左子树中；同理，第2种情况，LCA一定在当前结点的右子树中；而对于第3种和第4种情况，当前结点就是LCA。代码如下，该算法时间复杂度为O(h)，其中h为BST的高度。
struct node *LCA(struct node *root, struct node *p, struct node *q) {
if (!root || !p || !q) return NULL;
if (max(p->data, q->data) < root->data) //case 1）
return LCA(root->left, p, q);
else if (min(p->data, q->data) > root->data) //case 2）
return LCA(root->right, p, q);
else
return root; // case 3）and case 4）
}
2. 该二叉树每个结点包含一个指向父结点的指针，根结点的父结点为NULL。其结构如下:
struct node {
int data;
struct node* left;
struct node* right;
struct node* parent;
};
同样，该二叉树不一定是二叉搜索树(BST)。在前面文章中的自底向上的方法，可以在O(N)的时间之内找到LCA，不过由于本文中的二叉树有指向父结点的指针，所以并不用递归实现，求解应该更加简单。给定一棵二叉树如下：
_______3______
/ \
___5__ ___1__
/ \ / \
6 _2_ 0 8
/ \
7 4
可以从两个结点的位置开始向上回溯到根结点，最终这两个结点会合并成一条路径。可以使用一个hash_set来记录已经访问过的结点，如果在回溯的过程中访问到一个已经访问过的结点，则该结点一定是LCA，直接返回即可。该方法由于使用hash_set，因此需要额外的存储空间。时间复杂度为O(h)，h为二叉树的高度。
由于每个结点都有指向父结点的指针，因此可以求出这两个结点的高度差dh。可以看到，在回溯的过程中离根结点近的结点总是领先离根结点远的结点的dh步。这样，可以让离根结点远的（更深的结点）先走dh步，然后两个结点一起走，最终一定会在某一个结点相遇，则相遇的结点为LCA。如果不相遇，表示这两个结点不在同一棵树中，则返回NULL(由于我们假定了两个结点都在二叉树中，所以这种情况不可能出现)。
int getHeight(Node *p) {
int height = 0;
while (p) {
height++;
p = p->parent;
}
return height;
}
// 因为root->parent= NULL，所以参数中不需要传递root
Node *LCA(Node *p, Node *q) {
int h1 = getHeight(p);
int h2 = getHeight(q);
// 交换高度大小
if (h1 > h2) {
swap(h1, h2);
swap(p, q);
}
//保证h2>=h1
int dh = h2 - h1;
for (int h = 0; h < dh; h++)
q = q->parent;
while (p && q) {
if (p == q) return p;
p = p->parent;
q = q->parent;
}
return NULL; // p和q不在同一棵树中，这种情况在本题中不会出现。
}
3. 普通二叉树
前面我们提过如果结点中有一个指向父结点的指针，我们可以把问题转化为求两个链表的共同结点。现在我们可以想办法得到这个链表。
/
// 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)。
| 
转播
