如何获得从根到二叉树上给定节点的路径? [英] how to get the path from root to a given node on a binary tree?

问题描述

我正在尝试找出如何从根到二叉树上给定节点的路径.

I am trying to find out how to get the path from root to a given node on a binary tree.

它不是二进制搜索树.

It is not binary search tree.

每个非叶节点只有两个指向其子节点的指针.

Each non-leaf node has only two pointers to their children.

按顺序，前顺序，后顺序遍历不起作用.

In-order, pre-order, post-order traversal do not work.

我已尝试进行预订，但无法弄清楚该如何做.例如，我们有一棵二叉树: 它不是二进制搜索树.我们使用排序顺序节点使查找路径更加容易.

I have tried to do pre-order but cannot figure out how. For example, we have a binary tree: It is NOT a binary search tree. We use the sorting order node to make it easier to find the path.

     1 
   /   \
  2     3
 / \   / \
4   5 6   7 

我们想找到1到7的路径:

We want to find the path from 1 to 7:

通过预订，我们可以:

1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 

从流中，我们获得从1-> 7的路径，上面有所有节点.

From the flow, we get the path from 1 -> 7 with all nodes on it.

不应该这样.

我们非常感谢您的帮助.

Any help is really appreciated.

推荐答案

预遍历，也称为深度优先搜索确实有效.

Preorder traversal, otherwise known as depth-first search does work.

• 如果您递归实现预遍历遍历，那么当到达所需节点时，您可以展开堆栈(递归调用)并反向构造路径.

• If you implement preorder traversal recursively, then when you reach the desired node, you can unwind your stack (of recursive calls) and construct your path in reverse.

如果您以非递归方式实现预遍历遍历，那么您将直接构建堆栈，因此在这种情况下，一旦到达所需的节点，您就已经拥有了路径.

If you implement the preorder traversal non-recursively, then you will be building a stack directly, so in this case once you reach your desired node you have your path already.

在上述问题中的树中，查找从1到7的路径的算法如下.

In the tree in your question above, the algorithm to find the path from 1 to 7 proceeds as follows.

• 从1开始，将其推入堆栈，堆栈现在为[1]
• 向左转到2，将其推入堆栈，堆栈现在为[1 2]
• 向左转到4，将其推入，堆栈现在为[1 2 4]
• 没有4个孩子，这不是您想要的，所以弹出它，现在堆栈为[1 2]
• 现在您回到2了，您已经向左走，现在向右走，堆栈现在为[1 2 5]
• 没有5个孩子，所以现在弹出的堆栈为[1 2]
• 您已经用尽了2个孩子，所以将其弹出，堆栈现在为[1]
• 现在您回到第一个位置，并且您已经完成了左边的操作，因此请向右转到第3个位置，将其推入，现在堆栈为[1 3]
• 向左走，堆栈现在为[1 3 6]
• 6是一片叶子，不是您要寻找的叶子，所以弹出式堆栈为[1 3]
• 现在您必须从3开始向右移动，将其推入，现在堆叠为[1 3 7]
• 但是等等！看！您已到达要查找的节点！看看你的筹码！这就是您想要的路径.

• Start with 1, push it on the stack, stack is now [1]
• Go left to the 2, push it on the stack, stack is now [1 2]
• Go left to the 4, push it, stack is now [1 2 4]
• There are no children of 4, and it is not what you want, so pop it, stack is now [1 2]
• Now that you are back at the 2, and you have already gone left, now go right, stack is now [1 2 5]
• There are no children of 5, so pop, stack is now [1 2]
• You have exhausted the children of 2, so pop it, stack is now [1]
• Now you are back at the 1 and you have finished the left, so go right to the 3, push it, stack is now [1 3]
• Go left, stack is now [1 3 6]
• 6 is a leaf, not what you are looking for, so pop, stack is [1 3]
• Now you have to go to the right from 3, push it, stack is now [1 3 7]
• But WAIT! LOOK! You have arrived at the node you are looking for! And look at your stack! It's the path you want.

这篇关于如何获得从根到二叉树上给定节点的路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！