Python中查找从根到节点的路径

给定一个具有不同节点（没有两个节点的具有相同数据值）的二叉树。问题是打印从根到节点 x 的路径。如果节点 x 不存在，则打印“无路径”。

示例

输入

输出

1->2->5

方法 - 1

创建一个递归函数，该函数遍历二叉树中的不同路径以找到所需的节点 x。如果节点 x 存在，则返回 true，并将节点累积到某个数组 arr[] 中。否则，返回 false。

在遍历二叉树时，我们可以发现以下情况：

如果根节点为 null，则返回 false。这是递归函数的基准条件。

我们将根节点的值推入 arr[]。

如果 root 的 data = x，则返回 true。

如果节点 x 存在于根的左子树或右子树中，则返回 true。

否则，从 arr[] 中移除根节点的值并返回 false。

在第一种方法中，我们将使用递归函数。

此递归函数可以从另一个函数访问，以检查节点 x 是否存在，如果存在，则可以从 arr[] 访问路径节点。您可以全局定义 arr[] 或将其引用传递给递归函数。

下面是实现此方法的代码。

代码

输出

9 -> 1 -> 3 -> 4

时间复杂度：此方法具有线性时间复杂度，即 O(N)。这里 N 是二叉树中的节点数。

空间复杂度：程序将占用 O(H)。空间是存储递归函数栈所必需的。

这是解决此问题的方法之一。但是，可能存在其他方法可以找到从根到特定节点的路径。不同的方法具有不同的时间和空间复杂度。最佳方法应具有优化的复杂度，以确保程序的效率。