首页 > 代码库 > 剑指offer (24) BST的先序或后序遍历序列的正确性

剑指offer (24) BST的先序或后序遍历序列的正确性

2024-07-09 06:04:28   222人阅读

题目：输入一个整数数组，判断该数组是不是某个二叉搜索树的后序遍历序列

假设输入的数组的数字均不相同

 

解题分析：

对于二叉搜索树，中序序列一定是升序的，我们将后序遍历序列排序，结果即为 中序遍历序列

如果该后序遍历序列是正确的，那么 由 中序遍历序列和后序遍历序列 一定可以构建一棵二叉树

如果不能成功构建一棵二叉树，那么该后序遍历序列一定是错误的

 

题目即转化为 由 后序遍历序列和中序遍历序列构建一棵二叉树

主要思路就是 在中序中找根节点然后划分左右子树

详见笔者博文：http://www.cnblogs.com/wwwjieo0/p/3718779.html

 

 

bool IsPreorder(int* preVec, int length){    if (preVec == NULL || length < 0) return false;    if (length == 0) return true;  // 空树仍然true    int root = preVec[0];        // 在BST中 左子树的结点值小于根节点    int i = 1;    for (; i < length; ++i) {        if (preVec[i] > root) {            break;        }    }     // 在BST中 右子树的结点值小于根节点    int j = i;    for (; j < length; ++j) {        if (preVec[j] < root) {            return false;        }    }        bool left = IsPreorder(preVec + 1, i - 1);        // i = 1时，左子树为空，仍为true    bool right = IsPreorder(preVec + i, length - i);  // i = length时，左子树为空，仍为true    return (left && right);}

 

bool IsPostorder(int* postVec, int length){    if (postVec == NULL || length < 0) return false;    if (length == 0) return true;  // 空树仍为true    int root = postVec[length - 1];       // 在BST中 左子树的结点值小于根节点    int i = 0;    for (; i < length - 1; ++i) {        if (postVec[i] > root) {            break;        }    }    // 在BST中 右子树的结点值小于根节点    int j = i;    for (; j < length - 1; ++j) {        if (postVec[j] < root) {            return false;        }    }    bool left = IsPostorder(postVec, i);                   // i = 0时，左子树为空，仍为true    bool right = IsPostorder(postVec + i, length - i - 1); // i = length - 1时，右子树为空，仍为true    return (left && right);}

 


联系
我们