首页 > 代码库 > 9判断整数序列是不是二元查找树的后序遍历结果
9判断整数序列是不是二元查找树的后序遍历结果
转载请注明出处：http://www.cnblogs.com/wuzetiandaren/p/4252095.html
声明：现大部分文章为寻找问题时在网上相互转载，此博是为自己做个记录记录，方便自己也方便有类似问题的朋友，本文的思想也许有所借鉴，但源码均为本人实现，如有侵权，请发邮件表明文章和原出处地址，我一定在文章中注明。谢谢。
题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。
解题思路：
1.输入一个整型数组a，根据该数组创建二叉排序树，即二元查找树。
2.后序遍历遍历该二叉排序树，将结果保存到另一个整形数组b。
3.输入一个待比较的整型数组c，比较b和c里面的值是否相等。比较的方法：
a.如果b和 c的长度不相等，返回false。
b.否则，循环遍历b和 c中的元素，若有一个不相等则结束比较，返回false。
c.否则，返回true。
java实现：
1 package com.interview; 2 3 /** 4 * 判断整数序列是不是二元查找树的后序遍历结果 5 * @author wjh 6 * 7 */ 8 public class _9IsLRDTraversal { 9 10 /** 11 * @param args 12 */ 13 private static int k=0; 14 public static void main(String[] args) { 15 int[] a = {56,45,47,67,35,76,22,89,91,27,11,21,19,87}; 16 int[] b = new int[a.length]; //用于保存以a创建的二叉树的后序遍历结果 17 int[] c = {19, 22, 11, 27, 22, 35, 47, 45, 87, 91, 89, 76, 67, 56 }; 18 Node root = null; 19 root = createTree( root, a); //1)建树 20 System.out.println("打印想要比较的整数序列："); 21 printArr(c); //2)印想要比较的证书序列 22 System.out.println("二叉树的后序遍历结果："); 23 postOrder(root,b); //3)打印后序遍历结果 24 System.out.println(); 25 boolean result = compare(b, c); //4)比较是否相等 26 System.out.println("比较结果："+result); //5)打印比较结果 27 28 } 29 30 //判断输入的整数序列是不是二元查找树的后序遍历结果 31 private static boolean compare(int[] b, int[] c){ 32 int blength = b.length; 33 int clength = c.length; 34 if(blength!=clength){ 35 System.out.println("输入的数据与二叉树的长度不一致，不是该二叉树的后序遍历结果！"); 36 return false; 37 } 38 for(int i=0;i<blength;i++){ 39 if(b[i]!=c[i]){ 40 System.out.println("输入的数据与该二叉树后序遍历结果不一致，不是该二叉树的后序遍历结果！"); 41 return false; 42 } 43 } 44 System.out.println("输入的数据与该二叉树后序遍历结果一致！"); 45 return true; 46 } 47 48 49 //创建二叉排序树 50 public static Node createTree(Node root, int[] r){ 51 int n = r.length; 52 System.out.println("建树过程(a<--b表示在a的左边插入b;a-->b表示在a的右边插入b)："); 53 for(int i=0;i<n;i++){ 54 Node child = new Node(r[i],null,null); 55 root = insert(root, child); 56 } 57 return root; 58 } 59 60 61 //二叉排序树的插入算法 62 public static Node insert(Node root, Node child){ 63 //寻找插入位置 64 if(root==null){ 65 root = child; 66 System.out.println(root.data); 67 } 68 else 69 if(root.data>child.data){ 70 System.out.print(root.data+"<--"); 71 root.left = insert(root.left, child); 72 } 73 else{ 74 System.out.print(root.data+"-->"); 75 root.right = insert(root.right,child); 76 } 77 return root; 78 } 79 80 81 //二叉树的后序遍历 82 public static void postOrder(Node root,int[] b){ 83 if(root==null){ 84 return; 85 } 86 else{ 87 postOrder(root.left,b); 88 postOrder(root.right,b); 89 System.out.print(root.data+" "); 90 b[k++] = root.data; 91 } 92 } 93 94 //打印数组 95 private static void printArr(int[] a){ 96 int n = a.length; 97 for(int i=0;i<n;i++){ 98 System.out.print(a[i]+" "); 99 }100 System.out.println();101 }102 103 104 //节点的数据结构105 private static class Node {106 public int data;107 public Node left; //指向左子树108 public Node right; //指向右子树109 public Node() {110 super();111 // TODO Auto-generated constructor stub112 }113 public Node(int data, Node left, Node right) {114 super();115 this.data =http://www.mamicode.com/ data;116 this.left = left;117 this.right = right;118 }119 } 120 }
运行结果：
1. 因长度不相等：
建树过程(a<--b表示在a的左边插入b;a-->b表示在a的右边插入b)：
56
56<--45
56<--45-->47
56-->67
56<--45<--35
56-->67-->76
56<--45<--35<--22
56-->67-->76-->89
56-->67-->76-->89-->91
56<--45<--35<--22-->27
56<--45<--35<--22<--11
56<--45<--35<--22<--11-->21
56<--45<--35<--22<--11-->21<--19
56-->67-->76-->89<--87
打印想要比较的整数序列：
19 21 11 27 22 35 47
二叉树的后序遍历结果：
19 21 11 27 22 35 47 45 87 91 89 76 67 56
输入的数据与二叉树的长度不一致，不是该二叉树的后序遍历结果！
比较结果：false
2.因内容不相等：
建树过程(a<--b表示在a的左边插入b;a-->b表示在a的右边插入b)：
56
56<--45
56<--45-->47
56-->67
56<--45<--35
56-->67-->76
56<--45<--35<--22
56-->67-->76-->89
56-->67-->76-->89-->91
56<--45<--35<--22-->27
56<--45<--35<--22<--11
56<--45<--35<--22<--11-->21
56<--45<--35<--22<--11-->21<--19
56-->67-->76-->89<--87
打印想要比较的整数序列：
19 22 11 27 22 35 47 45 87 91 89 76 67 56
二叉树的后序遍历结果：
19 21 11 27 22 35 47 45 87 91 89 76 67 56
输入的数据与该二叉树后序遍历结果不一致，不是该二叉树的后序遍历结果！
比较结果：false
3.是二元查找树的后序遍历结果：
建树过程(a<--b表示在a的左边插入b;a-->b表示在a的右边插入b)：
56
56<--45
56<--45-->47
56-->67
56<--45<--35
56-->67-->76
56<--45<--35<--22
56-->67-->76-->89
56-->67-->76-->89-->91
56<--45<--35<--22-->27
56<--45<--35<--22<--11
56<--45<--35<--22<--11-->21
56<--45<--35<--22<--11-->21<--19
56-->67-->76-->89<--87
打印想要比较的整数序列：
19 21 11 27 22 35 47 45 87 91 89 76 67 56
二叉树的后序遍历结果：
19 21 11 27 22 35 47 45 87 91 89 76 67 56
输入的数据与该二叉树后序遍历结果一致！
比较结果：true
9判断整数序列是不是二元查找树的后序遍历结果