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

本文主要是介绍124 二叉搜索树的后序遍历序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后续遍历结果。

递归方式求解：对于后续遍历而言，其顺序是左子节点->右子节点->根节点，而根据二叉搜索树的特点，左子树比根节点小，右子树比根节点大，对于根节点而言，其访问结果是:左子树所有节点->右子树所有节点->根节点。从而可以发现最后一个元素一定是根节点，且右子树所有节点访问均大于根节点的值，则第小于根节点(最后一个元素的值)的第一个元素即为左子树的开始点，此时该节点前面所有的节点均要小于跟节点的值，如果不满足则不是二叉搜索树的后序遍历。

public Boolean backOrder(int []nums,int begin,int end)
{
if(end<=begin){return true;}
int index=0;
for(int i=end-1;i>=0;i--)
{
if(nums[i]<nums[end]){break;}
}
for(int i=index;i>=0;i--)
{
if(nums[i]>nums[end]){return false;}
}
return backOrder(nums,0,i)&&backOrder(nums,i+1,end-1);
}
public Boolean BackOrder(int[]nums)
{
return BackOrder(nums,0,nums.length-1);
}

这篇关于124 二叉搜索树的后序遍历序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---