程序员代码面试指南 3.14：根据后序数组重建搜索二叉树

1、思路

• 二叉树的后序遍历为先左、再右、最后根的顺序，即二叉树的头节点值为数组的最后一个元素；

• 例如数组 [2, 1, 3, 6, 5, 7, 4]，比4小的部分为[2, 1, 3]，比4大的部分为[6, 5, 7]，再继续递归地判断这两部分子树。

2、代码

#include <iostream>
#include <vector>

using namespace std;

bool isPostOrder(vector<int>& nums, int st, int ed)
{
    if (st == ed)
    {
        return true;
    }

    //leftEnd 表示左子树最后一个节点的位置， rightBegin 表示右子树第一个节点的位置
    int leftEnd = -1, rightBegin = ed;

    for (int i = st; i < ed; ++ i)
    {
        if (nums[i] < nums[ed] )                     //比最后一个元素小，说明是左子树节点
        {
            leftEnd = i;                             //标记左子树最后一个节点位置
        }
        else
        {
            if (rightBegin == ed) rightBegin = i;    //标记右子树起始节点位置
        }
    }

    if (leftEnd == -1 || rightBegin == ed)           //当前节点只存在左子树或只存在右子树的情况
    {
        return isPostOrder(nums, st, ed - 1);
    }

    if (leftEnd != rightBegin - 1)                   //不合法的情况
    {
        return false;
    }

    //继续递归判断当前节点的左子树和右子树
    return isPostOrder(nums, st, leftEnd) && isPostOrder(nums, rightBegin, ed - 1);
}

int main()
{
    int n;
    cin >> n;

    vector<int> nums(n);
    for (int i = 0; i < n; ++ i)
    {
        cin >> nums[i];
    }

    if (isPostOrder(nums, 0, n - 1))
    {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }

    return 0;
}