挑战数据结构和算法面试题——二叉搜索树的后序遍历

题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。

分析:

根据二叉查找树的定义,二叉查找树或者是一棵空二叉树,或者是具有一下特性的二叉树:

  • 若它的左子树不为空,则左子树上的所有结点的值均小于根节点的值;
  • 若它的右子树不为空,则右子树上的所有结点的值均小于根节点的值;
  • 它的左右子树又分别是二叉查找树。

结合二叉树的后序遍历,则初始序列的最后一位为树的根节点。

方法:

bool judge_is_search_tree(int *a, int start, int end) {
  if (start == end) return true;
  if (start > end) return false;

  int root = a[end - 1];
  int i = start;
  while (i < end-1 && a[i] < root) i++;
  int pos = i;
  while (i < end-1) {
    if (a[i] < root) return false;
    i++;
  }

  bool left = judge_is_search_tree(a, 0, pos);
  bool right = judge_is_search_tree(a, pos, end-1);

  return left&&right;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏恰童鞋骚年

数据结构基础温故-4.树与二叉树(上)

前面所讨论的线性表元素之间都是一对一的关系,今天我们所看到的结构各元素之间却是一对多的关系。树在计算机中有着广泛的应用,甚至在计算机的日常使用中,也可以看到树形...

11930
来自专栏Java3y

二叉树就这么简单

一、二叉树就是这么简单 本文撇开一些非常苦涩、难以理解的概念来讲讲二叉树,仅入门观看(或复习)…. 首先,我们来讲讲什么是树: 树是一种非线性的数据结构,相对于...

54780
来自专栏Bingo的深度学习杂货店

Q112 Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path suc...

35770
来自专栏算法与数据结构

数据结构 单链表元素定位 PTA

由于这个很简单,他也貌似没要判断溢出,取巧突破 #include<stdio.h> #include<malloc.h> #include<stdlib.h> ...

21970
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题25二叉树中和为某一值的路径

本题详细的分析过程均在代码注释中: import java.util.Iterator; import java.util.Stack; /** * 题目:...

31250
来自专栏拭心的安卓进阶之路

Java 集合深入理解(6):AbstractList

今天心情比天蓝,来学学 AbstractList 吧! ? 什么是 AbstractList ? AbstractList 继承自 AbstractCollec...

245100
来自专栏青玉伏案

算法与数据结构(三) 二叉树的遍历及其线索化(Swift版)

前面两篇博客介绍了线性表的顺序存储与链式存储以及对应的操作,并且还聊了栈与队列的相关内容。本篇博客我们就继续聊数据结构的相关东西,并且所涉及的相关Demo依然使...

288100
来自专栏武培轩的专栏

剑指Offer-重建二叉树

题目描述 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,...

37980
来自专栏尾尾部落

[剑指offer] 二叉搜索树的第k个结点

给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8)中,按结点数值大小顺序第三小结点的值为4。

14820
来自专栏电光石火

java获取当前时间和前一天日期

String basePath = request.getScheme()+"://"+request.getServerName()+":"+request....

30380

扫码关注云+社区

领取腾讯云代金券