题目

https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
image.png

思路

二叉搜索树：根节点，大于左节点，小于右节点。

得到后序遍历结果，判断是否满足二叉搜索树的规则。

关键在于，如何找到根节点、及其左节点和右节点。

分析后续遍历，可知道最后一个数字是树根节点的值。

进一步地，划分左右节点。依据是根节点大于左节点，小于右节点。

代码

  1. class Solution:
  2.     def verifyPostorder(self, postorder: List[int]) -> bool:
  3.         # if not postorder:
  4.         #     return False
  5.         if len(postorder) <= 1:
  6.             return True
  8.         root = postorder[-1]
  10.         for ind, value in enumerate(postorder):
  11.             if value > root:
  12.                 left = postorder[:ind]
  13.                 if ind < len(postorder):
  14.                     right = postorder[ind:len(postorder)-1]
  15.                 else:
  16.                     right = []
  17.                 break
  18.         else:
  19.             left = postorder[:-1]
  20.             right = []
  21.         # print(root, left, right)
  22.         return all(num < root for num in left) and all(num > root for num in right) and self.verifyPostorder(postorder[:-1])
  1. class Solution:
  2.     def verifyPostorder(self, postorder: List[int]) -> bool:
  3.         length = len(postorder)
  4.         if length <= 1:
  5.             return True
  7.         root = postorder[length - 1] # 根节点
  9.         # 查找左节点，左节点的值应小于根节点
  10.         leftIndex = 0
  11.         while leftIndex < length - 1:
  12.             if postorder[leftIndex] > root:
  13.                 break
  14.             leftIndex += 1
  16.         # 判断右子树符合二叉搜索树规则
  17.         rightIndex = leftIndex
  18.         while rightIndex < length - 1:
  19.             if postorder[rightIndex] < root:
  20.                 return False
  21.             rightIndex += 1
  23.         # 判断左子树是不是二叉搜索树
  24.         # print('ok')
  25.         left = self.verifyPostorder(postorder[ : leftIndex])
  26.         right = self.verifyPostorder(postorder[leftIndex : rightIndex])
  28.         return left & right

扩展

重建二叉树也是同样的思路。
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Solution:
  9.     def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
  10.         if not inorder:
  11.             return None
  13.         root = TreeNode(preorder.pop(0))
  14.         index = inorder.index(root.val)
  15.         root.left = self.buildTree(preorder, inorder[:index])
  16.         root.right = self.buildTree(preorder, inorder[index+1:])
  17.         return root
  • 二叉树后序遍历
  • 输入一个整数数组，判断该数组是不是某二叉搜索树的前序遍历的结果。