理解从先序遍历构造树的伪代码

Question

我需要做一些类似于这个问题中描述的任务：
用给定的前序遍历构造树

有一个非常有用的答案在这里，但我不完全理解伪代码，所以我想知道是否有人可以帮助向我描述发生了什么。

k = 0 // Initialize
input = ... get preorder traversal vector from user ... // Get input
Reconstruct(T) // Reconstruct method with tree input
  if input[k] == N // If element of input is N
    T = new node with label N // Make a new node with label N in tree T
    k = k + 1  // Increment k for next loop (Is this whole thing a loop? or a method call?)
    Reconstruct(T.left) // ?????
    Reconstruct(T.right) // ?????
 else // If element of input is L
    T = new node with label L // Make a new node with label L in tree T
    T.left = T.right = null // ?????
    k = k + 1 // Increment k for next loop

我已经在评论中写下了我对事物的理解，如果有人能够检查我的理解是否正确以及问号位的作用，我将非常感激。另外，这个伪代码是否通过运行输入并在输入中遇到 L 时回溯来创建一棵新树？或者它正在重建现有的二叉树？

Answer 1

没有循环。 k 是一个全局范围的变量，可以在 Reconstruct(T) 中访问。它只是字符数组（输入字符串）的当前索引。

正如您引用的问题中所解释的（使用前序遍历构造树），正确的算法是先处理节点的左子节点，然后再处理右子节点，这就是您在if 的 true 部分。如果当前节点恰好是叶子L，则不要为其提供子节点并返回到调用函数。

此函数的作用是沿着树的左边缘，向所有 N 节点添加子节点，并且在字符串结束之前不向所有 L 节点（也称为叶子）添加子节点。

编辑：当伪代码的作者说 T.left = T.right = null 时，这意味着此时当前节点没有左或右子节点（因为它是叶子）。这只是一个断言，不一定需要出现在代码中。