首页 > 其他 > 详细

【剑指offer】二叉搜索树的后序遍历序列

时间:2018-07-13 21:23:19      阅读:183      评论:0      收藏:0      [点我收藏+]

一、题目:

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

二、思路:

      1.搜索二叉树的定义:一棵树的左子树的值都比根节点的值小,右子树的值都比根节点的值大,空子树不算搜索二叉树。(百度上说算,这道题说不算)

      2.思路分析:输入的是序列,那么序列的最后一个元素是根节点,我们要判断他的左右子树是否满足条件,第一步要找出左右子树,第二步判断左右子树是否满足与根节点值的关系,第三步判断左右子树是否是搜索二叉树。第一步的方法是,找出第一个>根的值,以此为分界线,左边是左子树,右边是右子树,注意左右子树可能没有。第二步的方法是左子树的最大值(最大值满足说明全部都满足)是否小于根的值且右子树的最小值是否大于根的值。第三步的方法是递归调用左右子树。

      3.注意事项:根弹出以后,要注意是否已经没有值了,如果没有值了就返回是;找左右子树的分界线时,要注意没有左右子树的情况,以及只有一个元素时能不能找准的情况。

三、代码:

    技术分享图片

 

【剑指offer】二叉搜索树的后序遍历序列

原文:https://www.cnblogs.com/EstherLjy/p/9307385.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!