剑指offer（23）——C++实现判断数组是否为二叉搜索树的后序遍历

小鱼儿 2024-04-18 10:14 9阅读 0赞

# 题目 #

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

# 概念 #

*  二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
 *  后序遍历：左-右-中

# 解题思路 #

二叉搜索树的后序遍历，数组的最后一个树一定是根节点，若存在左子树则，数组前半部分一定小于根节点，后半部分大于根节点；划分出左右子树后递归继续判断。

# 完整代码 #

/*23-判断数组是否为二叉搜索树的后序遍历*/
    #include<iostream>
    #include<vector>
    using namespace std;
    
    class Solution {
        
    public:
    	bool VerifySquenceOfBST(vector<int> sequence) {
        
    		if (sequence.empty()) return false;
    		vector<int> lefttree, righttree;//用来存放左右子树，进行递归操作
    		int length = sequence.size();
    		int root = sequence[length - 1];
    		//将数组根据root值分成两部分
    		int i = 0;
    		for (; i < length - 1; ++i)//左节点都比根节点小
    		{
        
    			if (sequence[i] > root)//找到右子树的第一个值
    				break;
    		}
    		int j = i;
    		for (; j < length - 1; ++j)//
    		{
        
    			if (sequence[j] < root)
    				return false;
    		}
    		//将两部分别分存放在连个数组中，进行递归
    		if (i != 0)
    		{
        
    			for (int l = 0; l < i; ++l)
    				lefttree.push_back(sequence[l]);
    		}
    		if (j != length - 2)
    		{
        
    			for (int r = j; j < length - 1; ++j)
    				righttree.push_back(sequence[r]);
    		}
    		//递归
    		bool left = true;
    		if (lefttree.size()>1)
    			left = VerifySquenceOfBST(lefttree);
    		bool right = true;
    		if (righttree.size() > 1)
    			right = VerifySquenceOfBST(righttree);
    		return (left&&right);		
    	}
    };
    
    int main()
    {
        
    	vector<int> sequence = {
         5,7,6,9,11,10,8 };
    	Solution s;
    	s.VerifySquenceOfBST(sequence);
    	return 0;
    }

# 编程问题 #

总是不知道循环或者条件改变时该用什么，哎，，