【力扣】剑指 Offer 33. 二叉搜索树的后序遍历序列

【力扣】剑指 Offer 33. 二叉搜索树的后序遍历序列

• 前言
• 一、题目分析
• • 1.1 题目描述
  • 1.2解题思路分析
• 二、代码实现
• 总结

---

前言

记录一下自己不同于网站题解的解题思路。

---

一、题目分析 1.1 题目描述

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

1.2解题思路分析

1. 因为为二叉搜索树，且任意两个数字都互不相同，则我们对后序遍历数组进行升序排序即可得到中序遍历数组。

2. 在得到中序遍历数组后，可根据节点所在中序遍历的位置确定其左右子树节点的个数，即可实现对后序遍历数组中某个节点得到其对应的左右子树节点。

3. 划分左右子树后，即可分别比较左右子树各点的数值与其根节点的数值大小来判断书否满足二叉搜索树的特点：
   左子树所有节点数值均小于根节点的数值；
   右子树所有节点数值均大于根节点的数值；

二、代码实现

class Solution {

    int[] postorder;
    int[] inorder;
    HashMap<Integer, Integer> map = new HashMap<>();
    public boolean verifyPostorder(int[] postorder) {
        this.postorder = postorder;
        inorder = postorder.clone();
        Arrays.sort(inorder);       //获取中序遍历数组
        for (int i=0; i< inorder.length; i++){ //将中序遍历数组及其对应下表存储至哈希表中便于查询
            map.put(inorder[i], i);
        }

        return recur(postorder.length - 1,0, postorder.length - 1);
    }

    boolean recur(int root,int left, int right) {
        if (left >= right) return true;   

        int i = map.get(postorder[root]); // 获取当前节点在中序遍历数组中的下标i
        int numOfLeft = i - left;    // 计算当前节点左子树节点的个数
        int numOfRight = right-i;    // 计算当前节点右子树节点的个数

        for (int j = root-1; j >= root-numOfRight; j--) {       // 判断当前节点的右子树所有节点是否满足其数值均大于当前节点的数值
            if (postorder[j] < postorder[root]) return false;   // 若不满足则返回false
        }

        for (int j = root-numOfRight-1; j>= root-numOfRight-numOfLeft;j--){ // 判断当前节点的左子树所有节点是否满足其数值均小于当前节点的数值
            if (postorder[j] > postorder[root]) return false;               // 若不满足则返回false
        }


        return recur(root-(right-i)-1,left, i-1) && recur(root-1, i+1, right); // 递归查询左右子树                                                                                        
    }

}

---

总结

时间复杂度 O(N ^2):
递归占用 O(N)，每次递归查询进行判断是否满足二叉搜索树特性占用O(N)，每层递归中搜索、计算子树节点个数 *** 作占用 O(1)，因此为O(N^2)。
空间复杂度 O(N) ：
哈希表占用O(N)额外空间；最差情况下（即当树退化为链表），递归深度将达到O(N) ，故空间复杂度为O(N)。
运行结果：
力扣奇怪的执行时间。。。。时间复杂度应该与k神第一种题解一致的。