首页 > 试题广场 >

根据后序数组重建搜索二叉树

[编程题]根据后序数组重建搜索二叉树
  • 热度指数：1993 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个有 n 个不重复整数的数组 arr，判断 arr 是否可能是节点值类型为整数的搜索二叉树后序遍历的结果。

输入描述:
第一行一个整数 n，表示数组的长度。

第二行 n 个整数 arr_i。


输出描述:
如果是搜索二叉树后序遍历的结果则输出 "true"，否则输出 "false"。
示例1

输入

3
1 3 2

输出

true

备注:

算法知识视频讲解
开通博客
头像 我要出去乱说
发表于 2022-06-29 09:20:23
1、思路 二叉树的后序遍历为先左、再右、最后根的顺序，即二叉树的头节点值为数组的最后一个元素； 例如数组 [2, 1, 3, 6, 5, 7, 4]，比4小的部分为[2, 1, 3]，比4大的部分为[6, 5, 7]，再继续递归地判断这两部分子树。 2、代码 #include <ios 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 WYJ96
发表于 2021-07-27 04:32:36
import java.io.*; import java.util.*; public class Main { //判断一个数组arr是否为搜索二叉树的后序遍历 /*后序遍历 左 右 根 搜索二叉树：左子树的节点值均比根小，右子树的节点值均比根大 递归 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 闫岩_2020
发表于 2020-06-21 12:22:22
import java.util.Scanner; public class Main {     public static void main(String[] args)&n 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

模拟 树
上传者：小小
难度：
7条回答 4755浏览

热门推荐

通过挑战的用户

查看代码

相关试题

根据后序数组重建搜索二叉树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号