【面试题24】二叉搜索树的后序遍历序列

【题目描述】

输入一个整数数组，判断该数组是不是某二叉搜索树的后续遍历的结果。假设输入的数组的任意两个数字都互不相等。

【解决方案】

后续遍历的最后一个结点为二叉树的根节点，根据BST的特性，数组中前半部分比根节点大的为其左子树的节点，比他小的为其右子树结点，可以递归解决。

考虑情况：

1. 完全二叉树；

2. 只有左子树或右子树的二叉树；

3. 只有一个结点的二叉树；

4. 输入的后序遍历的序列没有对应的一棵二叉树；

5. 输入为null；

我的代码实现，仅供参考：

 1         public static bool IsBST(int[] arr, int start, int end)
 2         {
 3             if (arr == null || end - start < 0)
 4                 return false;
 5 
 6             int root = arr[end];
 7 
 8             //在二叉搜索树中左子树的节点小于根结点
 9             int i = start;
10             for (; i < end; i++)
11             {
12                 if (arr[i] > root)
13                     break;
14             }
15 
16             //在二叉搜索树中的右子树的节点大于根结点
17             int j = i;
18             for (; j < end; j++)
19             {
20                 if (arr[j] < root)
21                     return false;
22             }
23 
24             //判断左子树是不是二叉树
25             bool left = true;
26             if (i - 1 > start)
27                 left = IsBST(arr, start, i - 1);
28 
29             //判断右子树是不是二叉树
30             bool right = true;
31             if (i < end - 1)
32                 right = IsBST(arr, i, end - 1);
33 
34             return left && right;
35         }

【相关题目】

输入一个整数数组，判断该数组是不是某二叉搜索树的前序遍历的结果。与上述类似，只不过序列第一个数为根结点。