如果面试题要求处理一棵二又树的遍历序列，则可以先找到二又树的根节点，再基于根节点把整棵树的遍历序列拆分成左子树对应的子序列和右子树对应的子序列，接下来再递归地处理这两个子序列。本面试题应用的是这种思路，面试题7“重建二又树”应用的也是这种思路。

Question

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：

    5
   / \
  2   6
 / \
1   3

示例 1：

输入: [1,6,3,2,5]
输出: false

示例 2：

输入: [1,3,2,6,5]
输出: true

测试用例

功能测试（输入的后序遍历序列对应一棵二又树，包括完全二叉树、所有节点都没有左/右子树的二叉树、只有一个节点的二叉树；输入的后序遍历序列没有对应一棵二叉树）。 特殊输入测试（指向后序遍历序列的指针为 nullptr 指针）。

本题考点

考查应聘者分析复杂问题的思维能力。能否解决这道题的关键在于应聘者是否能找出后序遍历的规律。一旦找到了规律，用递归的代码编码相对而言就简单了。在面试的时候，应聘者可以从一两个例子入手，通过分析具体的例子寻找规律。 考查应聘者对二叉树后序遍历的理解。

Intuition

在后序遍历得到的序列中，最后一个数字是树的根节点的值。数组中前面的数字可以分为两部分：第一部分是左子树节点的值，它们都比根节点的值小；第二部分是右子树节点的值，它们都比根节点的值大。不满足第一部分小于根节点，第二部分大于根节点的情况，就不是某二叉搜索树的后序遍历结果。

以数组{5，7，6，9，11，10，8}为例，后序遍历结果的最后一个数字8就是根节点的值。在这个数组中，前3个数字5、7和6都比8小，是值为8的节点的左子树节点；后3个数字9、11和10都比8大，是值为8的节点的右子树节点。

检查是否满足上述条件的代码，可以通过递归来实现。

Code

import unittest
from typing import List

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        if len(postorder) == 1: return True  # 叶子节点
        if len(postorder) == 0:  return True  # 规定输入的list是空list时返回True

        root = postorder[-1]
        i = 0
        while postorder[i] < root:
            i += 1
        left_tree = postorder[:i]
        right_tree = postorder[i:-1]  # 注意这里的-1 要把root排除出去

        # 查看第二部分中有无小于根节点的情况，存在即返回False。
        for node in right_tree:
            if node < root:
                return False
        
        return self.verifyPostorder(left_tree) and self.verifyPostorder(right_tree)
        # 如果规定输入list = []，返回的是False，那么就要用下面三行代码。
        # left_res = self.verifyPostorder(left_tree) if len(left_tree) else True
        # right_res = self.verifyPostorder(right_tree) if len(right_tree) else True
        # return left_res and right_res

class TestSolution(unittest.TestCase):
    def setUp(self):
        self.test_class = Solution()

    def test_solution(self):
        postorder = [
            [4, 8, 6, 12, 16, 14, 10],  # 功能测试
            [4, 6, 7, 5],               # 功能测试
                                        # 边界值的测试
            []                          # 特殊样例
        ]
        answers = [
            True, True, True
        ]
        res = []
        for i in range(len(postorder)):
            res.append(self.test_class.verifyPostorder(postorder[i]))
        self.assertEqual(res, answers)
 
    def tearDown(self):
        del self.test_class


if __name__ == "__main__":
    unittest.main()

Extension

输入一个整数数组，判断该数组是不是某二叉搜索树的前序遍历结果。这和前面问题的后序遍历很类似，只是在前序遍历得到的序列中，第一个数字是根节点的值。

如果面试题要求处理一棵二又树的遍历序列，则可以先找到二又树的根节点，再基于根节点把整棵树的遍历序列拆分成左子树对应的子序列和右子树对应的子序列，接下来再递归地处理这两个子序列。本面试题应用的是这种思路，面试题7“重建二又树”应用的也是这种思路。