从特定叶子开始自下而上的树遍历

Question

我正在寻找一种从下到上遍历一棵树的方法，这样我就可以从我选择的特定叶子开始，然后继续到根。

预期输出：在链接示例树中的示例树图像中（取自此处），如果我指定从 Y 开始，算法将返回 YXZWVUT。

如果对此有任何帮助，我将不胜感激。

Answer 1

如果我正确理解了这个问题，这就是问题陈述

遍历一棵 n 叉树，从叶节点开始，一直到根，这样在遍历所有子节点之前不会遍历任何节点。第一个遍历的节点始终是叶节点，最后一个遍历的节点始终是根节点。

这可以通过使用两个递归函数来解决，TraverseUp() 是调用自身的主函数，另一个递归函数 PostOrderTraversal() 调用自身。数组 A 需要通过引用传递，并将包含最终遍历的列表。这是一些伪代码：

TraverseUp(Array *A, Node *n) {
  // Add n to A to maintain bottom up nature
  if (!n) return;
  A.add(n)

  // Go to parent
  Node *p = n.parent();
  if (!p) return;

  // For each child of p other than n, do a post order traversal
  foreach(Node *c in p.children) {
    if (c == n) continue;
    PostOrderTraversal(A, c);
  }
  // When done with adding all p's children, continue traversing up
  TraverseUp(A, p);
}

// Standard implementation of post order traversal
PostOrderTraversal(Array *A, Node *n) {
  if (!n) return;
  foreach(Node *c in n.children) {
    PostOrderTraversal(A, c);
    A.add(c);
  }
}