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

xiaoxiao2021-02-28  123

题目是关于二叉搜索树的后序遍历,我们需要了解二叉搜索树的左子树所有的值小于根节点,右子树的值大于根节点,而后序遍历数组的最后一个值为根节点,判定数组中小于根节点的为其左子树,大于根节点的为其右子树,然后就是其递归判定左子树和右子树;

牛客网剑指offer在线编程通过代码:

class Solution { public:     bool VerifySquenceOfBST(vector<int> sequence)      {          int length=sequence.size();          vector<int>s_left,s_right;          if(length==0)              return false;          int root=sequence[length-1];         int i=0;          for(i=0;i<length-1;i++)          {              if(sequence[i]>root)                  break;              s_left.push_back(sequence[i]);          }         int j=i;         for(;j<length-1;j++)         {             if(sequence[j]<root)                 return false;             s_right.push_back(sequence[j]);         }         bool left=true;         if(s_left.size()>0)           left=VerifySquenceOfBST(s_left);         bool right=true;         if(s_right.size()>0)         right=VerifySquenceOfBST(s_right);         return (left&&right);     } };

转载请注明原文地址: https://www.6miu.com/read-34514.html

最新回复(0)