最近公共祖先,用后序遍历c++
时间: 2024-09-30 16:07:39 浏览: 16
最近公共祖先(Root of Common Ancestors, RCA)是指在一个二叉树结构中,给定两个节点,找到它们的最深公共祖先。后序遍历是一种常见的二叉树遍历策略,在这种遍历顺序下,首先遍历左子树,然后右子树,最后访问根节点。
在C++中,如果我们已经得到了两个节点的后序遍历序列,可以利用这个信息重构出原始二叉树,并通过对比两个节点在重建后的树中的位置来确定它们的最近公共祖先。一种常见方法是使用两个栈,一个存储第一个节点的后序遍历路径,另一个存储第二个节点的后序遍历路径。当两个栈都不为空并且当前栈顶元素相同时,说明找到了一个公共节点,我们从这个节点开始向上追溯直到遇到空栈,这些节点就是它们的最近公共祖先。
下面是一个简单的伪代码示例:
```cpp
// 定义节点类 Node 和辅助函数
struct Node {
int val;
Node* left;
Node* right;
};
Node* buildTree(vector<int>& postorder, int start, int end) {
if (start > end) return nullptr;
int rootVal = postorder[end];
int index = -1;
for (int i = start; i < end; i++) {
if (postorder[i] == rootVal) index = i;
}
Node* node = new Node{rootVal};
node->left = buildTree(postorder, start, index - 1);
node->right = buildTree(postorder, index + 1, end - 1);
return node;
}
Node* findLCA(Node* root, vector<int>& path1, vector<int>& path2) {
stack<Node*> s1(path1.begin(), path1.end());
stack<Node*> s2(path2.begin(), path2.end());
while (!s1.empty() && !s2.empty()) {
if (s1.top()->val == s2.top()->val) {
root = s1.top();
s1.pop();
s2.pop();
} else {
if (s1.top()->val < s2.top()->val)
s1.pop();
else
s2.pop();
}
}
return root;
}
```
阅读全文