二叉搜索树的最近公共祖先给定一棵二叉搜索树的先序遍历序列,要求你找出任意两结点的最近公共祖先结点(简称 LCA)。
时间: 2024-06-14 12:04:35 浏览: 131
二叉搜索树(Binary Search Tree,简称BST)是一种特殊的二叉树,它的每个节点的值都大于其左子树中的所有节点的值,且小于其右子树中的所有节点的值。根据BST的特性,我们可以通过比较节点的值来确定最近公共祖先。
首先,我们需要根据给定的先序遍历序列构建二叉搜索树。构建BST的方法是从根节点开始,依次将序列中的元素插入到树中。如果插入的元素小于当前节点的值,则将其插入到左子树中;如果插入的元素大于当前节点的值,则将其插入到右子树中。
接下来,我们需要找出任意两个节点的最近公共祖先。最近公共祖先是指在二叉树中同时是这两个节点的祖先且深度最大的节点。为了找到最近公共祖先,我们可以从根节点开始遍历二叉搜索树,根据节点的值与给定两个节点的值的大小关系,不断更新当前节点为其左子树或右子树中的节点,直到找到最近公共祖先为止。
以下是一个示例代码,演示了如何构建二叉搜索树并找到任意两个节点的最近公共祖先:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildBST(preorder):
if not preorder:
return None
root = TreeNode(preorder[0])
i = 1
while i < len(preorder) and preorder[i] < root.val:
i += 1
root.left = buildBST(preorder[1:i])
root.right = buildBST(preorder[i:])
return root
def findLCA(root, p, q):
if not root:
return None
if p.val < root.val and q.val < root.val:
return findLCA(root.left, p, q)
elif p.val > root.val and q.val > root.val:
return findLCA(root.right, p, q)
else:
return root
# 示例输入
preorder = [6, 2, 0, 4, 3, 5, 8, 7, 9]
p = TreeNode(2)
q = TreeNode(8)
# 构建二叉搜索树
root = buildBST(preorder)
# 找到最近公共祖先
lca = findLCA(root, p, q)
print("最近公共祖先的值为:", lca.val)
```
输出结果为:
```
最近公共祖先的值为: 6
```
阅读全文