二叉搜索树的后序遍历序列

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

背景知识:
二叉搜索树(Binary Search Tree),又叫二叉排序树:或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。

算法描述:
将数列分为三段,最后一段是最后一个数,也是树的根;第一段小于根,第二段大于根:
| 小于根 | 大于根 | 根 |

然后小于根和大于根这两段又都是树,就可以递归求解了。
当树的大小为0或1时,返回true。

代码:
classSolution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size() == 0) {
            return false;
        }
        returnVerify(sequence);
    }

bool Verify(vector<int> sequence) {
        intsize = sequence.size();
        if(size <= 1) {
            return true;
        }

//开始切割数列
        vector<int> smaller;  //第一段,比root小
        vector<int> larger;      //第二段,比root大
        //根的值
        introot = sequence[size - 1];
        //判断此时是否还在第一段,若已经在第二段,但又回到了第一段
        //则返回false
        bool isOne = false;
        //如果第一个数小于root,则表明有第一段,isOne为true
        if(sequence[0] < root) {
            isOne = true;
        }
        for(inti = 0; i < size - 1; i++) {
            //比根小
            if(sequence[i] < root) {
                if(isOne == false) {
                    returnfalse;
                }
                smaller.push_back(sequence[i]);
            }
            //比根大
            else{
                if(isOne)
                    isOne = false;
                larger.push_back(sequence[i]);
            }
        }

returnVerify(smaller) && Verify(larger);
    }
};

总结:
应该多弄点测试用例,自己测试完后,再提交

二叉树的常见问题及其解决程序

【递归】二叉树的先序建立及遍历

Java中实现的二叉树结构

【非递归】二叉树的建立及遍历

二叉树递归实现与二重指针

二叉树先序中序非递归算法

轻松搞定面试中的二叉树题目

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/0d967083892aeed462eeb2bb129de58f.html