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

​

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

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

1
2
3
4
5

5
/ \
2 6
/ \
1 3

示例 1：

1
2

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

示例 2：

1
2

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

提示：

1

数组长度 <= 1000

解题方法

思路1：非递归

非递归，利用了性质：从任意一个结点k往左的这个子数组，比k大的都在右边，比k小的都在左边 [ […<k…] […>k…] k]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        //root > left  and right > root;
        int n= postorder.size();
        // leftNode 
        for(int i=0;i<n;i++) {
            bool leftNode = false;
            for(int j=i;j>=0;j--) {
                if(postorder[j] < postorder[i]) {
                    leftNode = true;
                }
                //has leftNode l
                bool rightNode = postorder[i] < postorder[j];
                if(leftNode && rightNode) {
                    return false;
                }

                 
            }
        }
        return true;
    }
};

方法二：递归定义

  • 根据二叉搜索树的定义，可以通过递归，判断所有子树的 正确性 （即其后序遍历是否满足二叉搜索树的定义） ，若所有子树都正确，则此序列为二叉搜索树的后序遍历。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        //root > left  and right > root;
        int n= postorder.size();
        return dfs(postorder,0,n-1);
    }


    bool dfs(vector<int> &v,int l,int r) {
        //valid l r 
        if (l>=r) return true;
        int root=l;
        while(v[root] < v[r]) root++;
        int i = root;
        while(v[i] > v[r]) i++;
        if(i!=r) {
            return false;
        }
        //remove root node
        return dfs(v,l,root-1) && dfs(v,root,r-1);


    }
};

方法三：单调栈

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        //root > left  and right > root;
        int n= postorder.size();
        if(n==0) return true;
        stack<int> s;
        int root = INT_MAX;
        for(int i=n-1;i>=0;i--) {
            //维护单调递增的序列=>  root=>right  ,遇到 left出栈
            //root 一定比 left 大，二叉搜索树的定义
            if(postorder[i] > root) return false;
            while(s.size()  && s.top() > postorder[i]) {
                root = s.top();
                s.pop(); //find rootNode
            }
            s.push(postorder[i]);
        }
        return true;
    }


     
};