理解伪代码从序遍历

Question

我需要做类似于这个问题描述的任务构建的东西树：
Construct tree with pre-order traversal given

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

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)内访问。它只是字符数组（输入字符串）的当前索引。

正如你提到的问题（Contsruct Tree with Pre-Order Traversal）解释说，正确的算法是做一个节点，然后在右孩子哪个是你的if的true节中看到的左孩子。如果当前节点碰巧是一片叶子，L，那么不要给它儿童并返回到调用函数。

此功能的作用是在树的左边缘之后，向所有N节点添加子节点，并且不向所有L节点（又名树叶）添加子节点，直到字符串结束。

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