《编程之美》读书笔记：第3.9节“重建二叉树”扩展问题2

 《编程之美》第3.9节“重建二叉树”
题目：如果已经知道了遍历的结果，能不能把一颗二叉树重新构造出来？

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

感谢azuryy为大家分享答案，原博客地址：http://hi.baidu.com/azuryy/blog/item/cc9e1017156d7f0fc93d6d16.html。

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

#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;
}