温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

如何理解大数据中二叉搜索树的后序遍历序列

发布时间:2021-12-09 16:43:06 来源:亿速云 阅读:132 作者:柒染 栏目:大数据

本篇文章给大家分享的是有关如何理解大数据中二叉搜索树的后序遍历序列,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话不多说,跟着小编一起来看看吧。

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

参考以下这颗二叉搜索树:

5
   / \
  2   6
 / \
1   3

示例 1:

输入: [1,6,3,2,5]
输出: false

示例 2:

输入: [1,3,2,6,5]
输出: true

提示:

  1. 数组长度 <= 1000

解题思路:

1,后续遍历的特点[左子树|右子树|根]

2,所以最后一个元素一定是根节点

3,从左往后遍历,找到第一个比根元素大的元素,从这个位置将数组拆成左右子数

4,判断右边子树,如果有元素比根元素大,那么不符合二叉搜索树的性质

5,递归遍历,直到叶子节点

6,对于这类题目是儿叉树和后续遍历的一个结合,主要考核对二叉树的理解

代码实现:

func verifyPostorder(postorder []int) bool {    if len(postorder)<=1{        return true    }        root:=postorder[len(postorder)-1]    fmt.Println(root,postorder)    right:=0;    for right<len(postorder)&&postorder[right]<root{        right++    }    for i:=right;i<len(postorder);i++{        if postorder[i]<root{            return false        }    }    return verifyPostorder(postorder[:right])&&verifyPostorder(postorder[right:len(postorder)-1])}

以上就是如何理解大数据中二叉搜索树的后序遍历序列,小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注亿速云行业资讯频道。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI