百度收录多的是哪些网站,建立虚拟网站,wordpress云音乐插件,wordpress悬浮目录问题描述#xff1a;输入一个整数数组#xff0c;判断该数组是不是某二叉搜索树的后续遍历结果。
递归方式求解#xff1a;对于后续遍历而言#xff0c;其顺序是左子节点-右子节点-根节点#xff0c;而根据二叉搜索树的特点#xff0c;左子树比根节点小#xf…问题描述输入一个整数数组判断该数组是不是某二叉搜索树的后续遍历结果。
递归方式求解对于后续遍历而言其顺序是左子节点-右子节点-根节点而根据二叉搜索树的特点左子树比根节点小右子树比根节点大对于根节点而言其访问结果是:左子树所有节点-右子树所有节点-根节点。从而可以发现最后一个元素一定是根节点且右子树所有节点访问均大于根节点的值则第小于根节点(最后一个元素的值)的第一个元素即为左子树的开始点此时该节点前面所有的节点均要小于跟节点的值如果不满足则不是二叉搜索树的后序遍历。
public Boolean backOrder(int []nums,int begin,int end)
{
if(endbegin){return true;}
int index0;
for(int iend-1;i0;i--)
{
if(nums[i]nums[end]){break;}
}
for(int iindex;i0;i--)
{
if(nums[i]nums[end]){return false;}
}
return backOrder(nums,0,i)backOrder(nums,i1,end-1);
}
public Boolean BackOrder(int[]nums)
{
return BackOrder(nums,0,nums.length-1);
}
