題目：輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果祝蝠，請(qǐng)重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字幻碱。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}绎狭，則重建出圖2.6所示的二叉樹并輸出它的頭結(jié)點(diǎn)。
public TreeNode BuildTree(int[] preorder, int[] inorder)
{
if (preorder.Length == 0 || inorder.Length == 0) return null;
var indexMap=new Dictionary<int,int>();
var length = preorder.Length;
for (int i = 0; i < length; i++)
{
indexMap.Add(inorder[i], i);
}
TreeNode root = BuildTree(preorder, 0, length - 1, inorder, 0, length - 1, indexMap);
return root;
}
public TreeNode BuildTree(int[] preOrder, int preOrderStart, int preOrderEnd, int[] inOrder, int inOrderStart,
int inOrderEnd, Dictionary<int, int> indexMap)
{
if (preOrderStart > preOrderEnd) return null;
var rootVal = preOrder[preOrderStart];
var root = new TreeNode(rootVal);
if (preOrderStart == preOrderEnd) return root;
var rootIndex = indexMap[rootVal];
var leftNodes = rootIndex - inOrderStart;
var rightNodes = inOrderEnd - rootIndex;
var leftSubtree = BuildTree(preOrder, preOrderStart + 1, preOrderStart + leftNodes, inOrder, inOrderStart, rootIndex - 1, indexMap);
var rightSubtree = BuildTree(preOrder, preOrderEnd - rightNodes + 1, preOrderEnd, inOrder, rootIndex + 1, inOrderEnd, indexMap);
root.left = leftSubtree;
root.right = rightSubtree;
return root;
}
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x)
{
val = x;
}
}
在二叉樹的前序遍歷序列中褥傍，第一個(gè)數(shù)字總是樹的根結(jié)點(diǎn)的值儡嘶。但在中序遍歷序列中，根結(jié)點(diǎn)的值在序列的中間恍风，左子樹的結(jié)點(diǎn)的值位于根結(jié)點(diǎn)的值的左邊蹦狂，而右子樹的結(jié)點(diǎn)的值位于根結(jié)點(diǎn)的值的右邊。因此我們需要掃描中序遍歷序列朋贬，才能找到根結(jié)點(diǎn)的值凯楔。
