如何将后订单的遍历堆栈实现转换为递归版本

Question

这是一个与分配有关的问题，但根据要求，他们没有要求如何实现它。输入表示如下：

        Input:
        5
        4  1  2
        2  3  4
        5 -1 -1
        1 -1 -1
        3 -1 -1
           4
          / 
         2   5
        / 
       1   3
        Output:
        1 3 2 5 4

其中5是总节点的数量，每一行代表根，左右节点。

这是我对邮政遍历的实现，这是更大类的一部分：

    private int n;
    private int[] _key;
    private int[] _left;
    private int[] _right;
    private List<int> PostOrder()
    {
        List<int> result = new List<int>(new int[n]);
        int counter = n-1;
        var stack = new Stack<int>();
        stack.Push(0);
        while (stack.Count > 0 && counter > 0)
        {
            int index = stack.Pop();
            result[counter] = _key[index];                
            int leftIndex = _left[index];
            int rightIndex = _right[index];
            if (leftIndex != -1)
                stack.Push(leftIndex);
            if (rightIndex != -1)
                stack.Push(rightIndex);
            counter--;
        }
        return result;
    }

我试图实现此实现的递归版本，但无法表现出我的进度。我知道该算法是如何以递归方式工作的：

   PostOrder(root)
   {
      PostOrder(root.left);
      PostOrder(root.right);
      Visit/Print(root);
   }

，但不确定当递归击中叶子时，我应该如何返回，因为所有数据都表示为数组？任何帮助或建议都将受到高度赞赏。

Answer 1

尝试以下类似：

private void PostOrder(result, index)
{
    if (index == -1)
        return;
    int leftIndex = _left[index];
    int rightIndex = _right[index];
    PostOrder(result, leftIndex);
    PostOrder(result, rightIndex);
    //Add element in Post-Order
    result.add(_key(index));
}

List<int> result = new List<int>();
PostOrder(result, 0);
//result will have the post-order sequence