扩展问题2：如何判定给定的前序遍历和中序遍历的结果是合理的呢？

感谢为大家分享答案，原博客地址：。

递归算法实现，分别遍历左右子树，递归中迭代查找左右子树的长度，类似于书中的方法。

#include <iostream>
#include <string>

using namespace std;

bool valid = true;

inline int find(char needle, const char* haystack, int start, int end )
{
const char* p = haystack + start;
int i = 0;
int offset = end - start ;

while ( p && i < offset )
{
if ( *p == needle )
{
if ( start != 0 )
return i + start;
else
return i;
}
p++, i++;
}
return -1;
}

void isValid( const char* preOrder, const char* inOrder, int start, int end )
{
if ( !valid )
return ;

int position = find( *preOrder, inOrder, start,end );
if ( position == -1 )
{
valid = false;
return ;
}

if ( start < position )
{
isValid( preOrder + 1, inOrder,start,position ); //在左子树中遍历
}

if ( position + 1 < end )
{
isValid( preOrder + position + 1, inOrder, position + 1, end ); //在右子树中遍历
}
}

// Two Simple Test Cases
int main()
{
string pre1 = "abdefc";
string mid1 = "dbfeac";

string pre2 = "abdefc";
string mid2 = "dcfeab";

isValid(pre1.c_str(),mid1.c_str(),0,mid1.length());
cout << valid << endl;    // 输出 true

valid = true;
isValid(pre2.c_str(),mid2.c_str(),0,mid2.length());
cout << valid << endl;   //输出false
return 0;
}