微软算法100题09 判断整数序列是不是二元查找树的后序遍历结果

9. 判断整数序列是不是二元查找树的后序遍历结果
题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true,否则返回false。
例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:
8
/ \
6 10
/ \ / \
5 7 9 11
因此返回true。
如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回false。

思路:如果一个数组为BST的后序遍历结果 则最后一个元素必然为该BST的根节点 因为BST的特性是左子树必然全部小于根节点,右子树全部大于根节点,则我们可以从数组倒数第二个元素开始往前遍历,直到找到第一个小于根节点的元素,则从数组第一个元素到该元素之间的所有元素为左子树(包含),该元素到根节点元素之间的元素为右子树(不包含),先分别遍历左子树元素和右子树元素,如果左子树中有大于根节点的元素,则不符合BST的定义,同理如果右子树元素中有小于根节点的元素,也不符合BST的定义,如果验证通过,则用上述逻辑递归校验左子树和右子树

 1 package com.rui.microsoft;
 2
 3 import java.util.Arrays;
 4
 5 public class Test09_IsBSTByPostOrder {
 6
 7     public static void main(String[] args) {
 8         //int[] origin = {5,7,6,9,11,10,8};
 9         int[] origin = {5,6,7,8,9,10,11};
10         //int[] origin = {7,4,6,5};
11         boolean flag = isBST(origin);
12         System.out.println(flag);
13     }
14
15     public static boolean isBST(int[] input){
16         boolean flag = false;
17         int n = input.length;
18         //n==0 means current tree is empty
19         if(n==1 || n==0) return true;
20         else{
21             //the last element in the post-order query array must be the root node
22             int root = input[n-1];
23             int line = n - 2;
24             //search the dividing line between left tree and right tree of the root
25             while(input[line] > root && line >= 0){
26                 line--;
27             }
28             //now the pointer line should be pointing to the last node of the leaf tree
29
30             int[] left = Arrays.copyOfRange(input, 0, line+1);
31             int[] right = Arrays.copyOfRange(input, line+1, n-1);
32
33             if(!checkLeft(left, root) || !checkRight(right, root)) return false;
34             if(isBST(left) && isBST(right))return true;
35         }
36
37         return flag;
38     }
39
40     private static boolean checkLeft(int[] left, int root){
41         for(int i : left){
42             if(i > root) return false;
43         }
44         return true;
45     }
46
47     private static boolean checkRight(int[] right, int root){
48         for(int i: right){
49             if(i < root) return false;
50         }
51         return true;
52     }
53 }
时间: 10-20

微软算法100题09 判断整数序列是不是二元查找树的后序遍历结果的相关文章

IT公司100题-9-判断整数序列是不是二元查找树的后序遍历结果

问题描述: 输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果. 如果是返回true,否则返回false. 例如输入4, 8, 6, 12, 16, 14, 10,由于这一整数序列是如下树的后序遍历结果: 10/     \6      14/  \    /   \4   8 12    16 因此返回true. 如果输入6, 5, 8, 5, 7 ,则返回false. 分析: 在后续遍历得到的序列中,最后一个元素为树的根结点.根节点元素将数组分为两部分,左边都小于根节点,右边都大

第9题:判断整数序列是不是二元查找树的后序遍历结果

欢迎转载,转载请务必注明出处:http://blog.csdn.net/alading2009/article/details/44872143 第9题:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果.如果是返回true,否则返回false. 例如输入5.7.6.9.11.10.8,由于这一整数序列是如下树的后序遍历结果: 因此返回true. 如果输入7.4.6.5,没有哪棵树的后序遍历的结果是这个序列,因此返回false. 由于二叉查找树的特性(左子树的值小于根节点,右子树的值

9判断整数序列是不是二元查找树的后序遍历结果

转载请注明出处:http://www.cnblogs.com/wuzetiandaren/p/4252095.html 声明:现大部分文章为寻找问题时在网上相互转载,此博是为自己做个记录记录,方便自己也方便有类似问题的朋友,本文的思想也许有所借鉴,但源码均为本人实现,如有侵权,请发邮件表明文章和原出处地址,我一定在文章中注明.谢谢. 题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果.如果是返回true,否则返回false. 解题思路: 1.输入一个整型数组a,根据该数组创建二

【编程题目】判断整数序列是不是二元查找树的后序遍历结果,如果是,构建该二元查找树

判断整数序列是不是二元查找树的后序遍历结果题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果.如果是返回 true,否则返回 false.例如输入 5.7.6.9.11.10.8,由于这一整数序列是如下树的后序遍历结果:8/ \6 10/ \ / \5 7 9 11因此返回 true.如果输入 7.4.6.5,没有哪棵树的后序遍历的结果是这个序列,因此返回 false. 做这个题目的时候最开始傻了,想着从前到后根据数字的大小关系判断.后来幡然醒悟,根据后序遍历的特点.序列最后一

判断一个序列是否是一个二叉查找树的后序遍历结果

题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果.如果是返回 true,否则返 回 false . 例如输入 5.7.6.9.11 .10.8,由于这一整数序列是如下树的后序遍历结果: 8 / \ 6 10 / \ / \ 5 7 9 11 因此返回 true. 如果输入 7.4.6.5,没有哪棵树的后序遍历的结果是这个序列,因此返回 false . 思路:对于树的很多问题都是可以使用递归来解决.这道题也不例外.首先明白后序遍历的特点,最后一个是根元素.左子树都比根元素打,右

微软算法100题88 将字符串中的字符&#39;*&#39;移到串的前部分

函数将字符串中的字符'*'移到串的前部分,前面的非'*'字符后移,但不能改变非'*'字符的先后顺序,函数返回串中字符'*'的数量.如原始串为:ab**cd**e*12,处理后为*****abcde12,函数并返回值为5.(要求使用尽量少的时间和辅助空间) 思路:类似于快速排序,用两个指针分别指向字符数组的左右边界,寻找左边第一个不为*的字符,寻找右边第一个*,然后交换字符,然后继续寻找和交换的过程,直到两个指针相交, 时间复杂度o(n), 空间复杂度o(1) 第一个写的程序有问题,没有考虑到保持

判断数组是不是某二叉搜索树的后序遍历

题目:输入一个数组,判断数组是不是某二叉搜索树的后序遍历.输入的数组的任意两个数字都不相同 分析:要明白题目的意思,意思就是判断一个数组是否是某个搜索树的后序遍历.首先要搞清搜索树的含义:跟结点大于左子树而小于右子树.其次,数组的最后一个结点一定是后序遍历的根节点.所以我们只要满足这两个条件,再通过递归就可以解出来了.代码如下: // 二叉搜索树的遍历序列.cpp : 定义控制台应用程序的入口点. // #include "stdafx.h" #include <iostream

已知二叉树的先序遍历序列和中序遍历序列,输出该二叉树的后序遍历序列

题目描述 输入二叉树的先序遍历序列和中序遍历序列,输出该二叉树的后序遍历序列. 输入 第一行输入二叉树的先序遍历序列: 第二行输入二叉树的中序遍历序列. 输出 输出该二叉树的后序遍历序列. 示例输入 ABDCEF BDAECF 示例输出 DBEFCA #include <iostream> #include <cstring> #define MAX 50+3 using namespace std; typedef char Elem_Type; typedef struct B

微软算法100题01 二叉搜索树转为双向链表

提高编程能力的最佳途径就是多写代码, 就让我们从现在开始吧! 1. 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表.要求不能创建任何新的结点,只调整指针的指向.       10      /    |   6     14 /   |     /  |4   8   12  16 转换成双向链表4=6=8=10=12=14=16. 二叉查找树的特点:任意节点的左子树都要小于当前节点:右子树都要大于当前节点.特点:查询某个值,需要的时间复杂度为O(lgN) 网上的解决方案大部分都是C