二叉搜索树路径合并代码示例

在数据结构和算法领域中，二叉搜索树（Binary Search Tree, BST）是一种广泛应用的数据结构。它具有许多重要的性质和操作方法，如插入、删除和查找等。本文将探讨一种与二叉搜索树相关的操作：路径合并，并提供相应的Python代码实现。

什么是路径合并？

路径合并是指在给定的二叉搜索树中找到两个节点之间的所有路径，并将这些路径合并成一个单一的列表或链表的操作。具体来说，假设我们有两个节点 node1 和 node2，路径合并的目标是生成从 node1 到根节点的一条路径以及从 node2 到根节点的一条路径。

实现思路

实现二叉搜索树路径合并的核心在于找到两个给定节点的最近公共祖先（Lowest Common Ancestor, LCA），之后分别构建从这两个节点到LCA的路径，再将这两条路径合并。具体步骤如下：

查找两个节点的最近公共祖先：遍历整个二叉搜索树，直到找到同时大于或小于给定两节点值的节点。
构造两条路径：利用深度优先搜索（Depth First Search, DFS）分别构建从每个目标节点到LCA的路径。
合并路径：将两个路径拼接成一条完整的路径。

代码实现

以下为一个简单的Python函数，用于实现上述算法：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def path_from_root_to_node(root, node_val, path=[]):
    if root is None:
        return False
    
    # If the current node's value matches with target node's value,
    # we consider this as one of the correct answer
    if root.val == node_val:
        path.append(root)
        return True

    # Search in left and right subtrees
    found_in_left = path_from_root_to_node(root.left, node_val, path)
    found_in_right = path_from_root_to_node(root.right, node_val, path)

    if found_in_left or found_in_right:
        path.append(root)
        return True
    
    # Current node does not have the value we are looking for,
    # so remove current from result and return False
    return False

def find_path_and_merge(node1, node2):
    root = TreeNode(5)  # Example with a simple tree. Modify as needed.
    root.left = TreeNode(3)
    root.right = TreeNode(7)
    root.left.left = TreeNode(2)
    root.left.right = TreeNode(4)
    
    path1 = []
    if not path_from_root_to_node(root, node1, path1):
        return None

    path2 = []
    if not path_from_root_to_node(root, node2, path2):
        return None
    
    # Find LCA of the two nodes
    current = root
    while current:
        if (node1 <= current.val and node2 >= current.val) or \
           (node1 >= current.val and node2 <= current.val):
            break
        elif node1 < current.val and node2 < current.val:
            current = current.left
        else:
            current = current.right
    
    path_to_lca = [current]
    
    # Reconstruct the paths from LCA to nodes.
    while path1[-1] != current:
        path1.pop()
        
    while path2[-1] != current:
        path2.pop()
        
    return path1 + path2

# Example usage
node1 = 4
node2 = 7
merged_path = find_path_and_merge(node1, node2)
print([x.val for x in merged_path])

上述代码中，find_path_and_merge 函数接收两个目标节点值作为输入，并返回从这两个节点到根节点路径的合并。通过递归查找两条路径并将它们合并在一起。

总结

本文介绍了二叉搜索树路径合并的基本概念、实现思路及Python代码示例。这种技术在某些场景下非常有用，如在复杂的数据结构中快速找到两个节点之间的最短距离或相似性等应用。希望上述内容对你有所帮助！