已知一颗二叉树的前序遍历和中序遍历求后序遍历

原理

---

一棵树的后序遍历等于左子树的后续遍历加上右子树的后序遍历再加上根节点。

思路

---

前序遍历结果字符串的第一个字符一定是这棵树的根节点。中序遍历的结果字符串以根节点为界限左右分别是左右子树的中序遍历结果leftTree和rightTree，这样我们还知道了左右子树的节点个数。通过左右子树的节点个数我们就可以从前序遍历中得到左右子树的的前序遍历。分别对左右子树递归这一过程即可。

代码实现(C#)

---

```

using System;

class Program {

    static void Main (string[] args) {

        string preOrder = "ABDGHECKFIJ";

        string inOrder = "GDHBEAKCIJF";

        string posetOrderResult = GetPostOrder (preOrder, inOrder);

        Console.WriteLine (posetOrder);

    }

    public static string GetPostOrder (string preOrder, string inOrder) {

        //如果是叶子节点即可返回

        if (preOrder.Length <= 1) {

            return preOrder;

        }

        //取得根节点

        string root = preOrder.Substring (0, 1);

        //通过根节点得到左右子树

        string[] trees = inOrder.Split (root);

        string leftInOrder = trees[0];

        string rightInOrder = trees[1];

        //根据左右字数的节点个数得到前序遍历

        string leftPreOrder = preOrder.Substring (1, leftInOrder.Length);

        string rightPreOrder = preOrder.Substring (leftInOrder.Length + 1, rightInOrder.Length);

        //递归

        return GetPostOrder (leftPreOrder, leftInOrder) + GetPostOrder (rightPreOrder, rightInOrder) + root;

    }

}

```

后记

---

如果知道后序遍历和中序遍历求前序遍历道理是一样的只不过变成了根节点加左子树的前序遍历加右子树的前序遍历。但是知道前序遍历和后序遍历没法得到中序遍历，因为我们不能确定左右子树的节点个数。