微信公众号：路人zhang
扫码关注微信公众号

回复“面试手册”，获取本站PDF版

回复“简历”，获取高质量简历模板

回复“加群”，加入程序员交流群

回复“电子书”，获取程序员类电子书

当前位置： 算法 > 剑指offer > 剑指offer 33.二叉搜索树的后序遍历序列

剑指offer 33.二叉搜索树的后序遍历序列

题目描述

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

参考以下这颗二叉搜索树：

     5
    / \
   2   6
  / \
 1   3

示例 1：

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

示例 2：

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

提示：

  1. 数组长度 <= 1000

题解

(二叉搜索树,DFS) O(n)

根据后序序列和二叉搜索树的特性，在构造二叉搜索树（并不需要创建出真正的节点）的过程中判断是否出现矛盾，我们知道二叉搜索树的左子树的值要小于右子树，否则就不是一棵二叉搜索树。

如何构造二叉搜索树呢？

  1. 根节点：后序序列的最后一个元素就是根节点
  2. 而左子树中的值都是小于根节点的，所以从前往后遍历序列就可以找到第一个大于根节点的位置 k，从 [l, k – 1] 就是左子树，[k, r) 就是右子树

如何判断矛盾？

  • 只要判断 [k, r) 中的值是否都大于根节点即可

时间复杂度

O(n)

空间复杂度

O(n)

C++ 代码

class Solution {
public:
    bool dfs(vector<int>& postorder, int l, int r) {
        if (l >= r) return true;
        int root = postorder[r];
        int k = l;
        while (k < r && postorder[k] < root) k ++ ;
        for (int i = k; i < r; i ++ )
            if (postorder[i] < root)
                return false;
        return dfs(postorder, l, k - 1) && dfs(postorder, k, r - 1);
    }

    bool verifyPostorder(vector<int>& postorder) {
        if (postorder.empty()) return true;
        return dfs(postorder, 0, postorder.size() - 1);
    }
};

Java 代码

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if (postorder == null || postorder.length == 0) {
            return true;
        }
        return dfs(postorder, 0, postorder.length - 1);
    }
    
    private boolean dfs(int[] postorder, int l, int r) {
        if (l >= r) {
            return true;
        }
        int root = postorder[r];
        int k = l;
        while (k < r && postorder[k] < root) {
            k++;
        }
        for (int i = k; i < r; i ++ ) {
            if (postorder[i] < root) {
                return false;
            }
        }
        return dfs(postorder, l, k - 1) && dfs(postorder, k, r - 1);
    }
}

Python 代码

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        if not postorder:
            return True
        return self.dfs(postorder, 0, len(postorder) - 1)
    
    def dfs(self, postorder: List[int], l: int, r: int) -> bool:
        if l >= r:
            return True
        root = postorder[r]
        k = l
        while k < r and postorder[k] < root:
            k += 1
        for i in range(k, r):
            if postorder[i] < root:
                return False
        return self.dfs(postorder, l, k - 1) and self.dfs(postorder, k, r - 1)

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer