首页 > 代码库 > 剑指Offer之二叉搜索树的后序遍历序列
剑指Offer之二叉搜索树的后序遍历序列
题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
基本思路
在后序遍历得到的序列中，最后一个数字是树的根节点的值。数组中前面的数字可以分为两部分：第一部分是左子树节点的值，它们都比根节点的值小；第二部分是右子树节点的值，他们都比根节点的值大。
以数组{5,7,6,9,10,8}为例，后序遍历结果的最后一个数字8就是根节点的值。在这个数组中，前3个数字5，7和6都比8小，是值为8的节点的左子树节点；后3个数字9,11和10都比8大，是值为8的节点的右子树节点。
接下来用同样的方法确定与数组每一部分对应的子树的结构，这其实是一个递归的过程。对于序列5,7,6，最后一个数字6是左子树的根节点的值。数字5比6小，是值为6的节点的左子树，而7则是它的右子节点。同样，在序列9,11,10中，最后一个数字10是右子树的根节点，数字9比10小，是值为10的节点的左子节点，而11则是它的右子节点。
分析另一个整数数组{7,4,6,5}。后序遍历的最后一个数字是根节点，因此根节点的值是5。由于第一个数字7大于5，因此对应的二叉搜索树中，根节点没有左子树，数字7，4和6都是右子树的节点的值。但右子树中有一个值为4的节点，比根节点的值5小，违背了二叉搜索树的定义。因此不存在一棵二叉搜索树，它的后序遍历序列是7,4,6,5。
Java代码
package com.swordOffer.sequenceOfBST15;import java.util.Scanner;/** * Created by Feng on 2017/5/14. * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。 * 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 */public class SequenceOfBST { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt();//数组的大小 int[] postOrder = new int[n]; for (int i = 0; i < n; i++) { postOrder[i] = sc.nextInt(); } boolean result = verifySquenceOfBST(postOrder); if (result) { System.out.println("Yes"); } else { System.out.println("No"); } } } public static boolean verifySquenceOfBST(int[] sequence) { if (sequence.length <= 0) { return false; } return isTreeBST(sequence, 0, sequence.length - 1); } private static boolean isTreeBST(int[] sequence, int start, int end) { //如果至多只有一个元素 if (end <= start) { return true; } int i = start; //在二叉树搜索中左子树的节点小于根节点 for (; i < end; i++) { if (sequence[i] > sequence[end]) { break; } } //在二叉树搜索树中右子树的节点大于根节点 for (int j = i; j < end; j++) { if (sequence[j] < sequence[end]) { return false; } } return isTreeBST(sequence, start, i - 1) && isTreeBST(sequence, i, end - 1); }}
剑指Offer之二叉搜索树的后序遍历序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。