题解 | #二叉搜索树的后序遍历序列#

题目的主要信息：

• 题目给出我们一个一维数组sequence
• 该数组需要我们判定数组sequence中的元素是否符合一个二叉搜索树的后序遍历顺序
• 如果该数组sequence可以是一种二叉搜索树的后序遍历顺序，则返回true
• 如果该数组sequence非二叉搜索树的后序遍历顺序，则返回false

举一反三：

学习完本题的思路你可以解决如下题目：

单调栈相关

JZ9. 用两个栈实现队列

JZ30. 包含min函数的栈

JZ31. 栈的压入、弹出序列

后序遍历相关

JZ37. 序列化二叉树

方法一：单调栈（推荐使用）

知识点：栈

栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

思路：单调栈 首先我们需要按照题目给出列表的逆序进行遍历，这样我们的遍历视角转成了$[\mathrm{根}-\mathrm{右}\mathrm{子}\mathrm{树}-\mathrm{左}\mathrm{子}\mathrm{树}][根-右子树-左子树]$。假定原输入列表的顺序为$[t_n,t_{n_1},\mathrm{.}\mathrm{.}\mathrm{.},t_2,t1][t\_n,\; t\_\{n\_1\},...,t\_2,\; t1]$，则该逆序后列表内容$[t_0,t_1,t_2,\mathrm{.}\mathrm{.}\mathrm{.},t_n][t\_0,\; t\_1,\; t\_2,...,t\_n]$有如下特性：

1. 当时，说明节点$t_{i+1}t\_\{i+1\}$是$t_{i}t\_i$的右子节点
2. 当$t_i>t_{i+1}t\_i\; >\; t\_\{i+1\}$时，说明节点$t_{i+1}t\_\{i+1\}$是已经遍历过的所有节点中比$t_{i+1}t\_\{i+1\}$大的且最接近$t_{i+1}t\_\{i+1\}$的节点的左子节点，设$t_{i+1}t\_\{i+1\}$对应的该父节点为$rootroot$。同时要满足$t_{i+1},t_{i+2},\mathrm{.}\mathrm{.}\mathrm{.},t_{n}t\_\{i+1\},t\_\{i+2\},...,t\_n$都要比$rootroot$小。
3. 根据我们推理的以上性质（加粗部分），用单调栈工具进行操作，如果能找到不符合以上性质的矛盾点，则返回false，如果上述性质都满足，则返回true

具体做法：

• step 1：首先处理特殊情况，sequence为空的情况，返回false
• step 2：维护一个单调栈s，不断迭代一个根节点root（初始化为INT_MAX）
• step 3：通过循环反向遍历给定的列表，模拟逆序操作
• step 4：循环内，如果当前遍历节点大于root，则返回false
• step 5：如果当前节点小于栈顶节点且栈非空，则内循环更新root，并不断退栈，这一过程在找到当前节点的父节点
• step 6：内循环结束后，将数字进入单调栈

图示：

Java实现代码：

import java.util.*;
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        // 处理序列为空情况
        if(sequence.length == 0) return false;
        Stack<Integer> s = new Stack<>();
        int root = Integer.MAX_VALUE;
        // 以根，右子树，左子树顺序遍历
        for(int i = sequence.length - 1; i >= 0; i--) {
            // 确定根后一定是在右子树节点都遍历完了，因此当前sequence未遍历的节点中只含左子树，左子树的节点如果>root则说明违背二叉搜索的性质
            if(sequence[i] > root) return false;
            // 进入左子树的契机就是sequence[i]的值小于前一项的时候，这时可以确定root
            while(!s.isEmpty() && s.peek() > sequence[i]) {
                root = s.pop();
            }
            // 每个数字都要进一次栈
            s.add(sequence[i]);
        }
        return true;
    }
}

C++实现代码：

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        // 处理序列为空情况
        if(sequence.size() == 0) return false;
        
        stack<int> s;
        int root = INT_MAX;
        // 以根，右子树，左子树顺序遍历
        for(int i = sequence.size() - 1; i >= 0; i--) {
            // 确定根后一定是在右子树节点都遍历完了，因此当前sequence未遍历的节点中只含左子树，左子树的节点如果>root则说明违背二叉搜索的性质
            if(sequence[i] > root) return false;
            // 进入左子树的契机就是sequence[i]的值小于前一项的时候，这时可以确定root
            while(!s.empty() && s.top() > sequence[i]) {
                root = s.top();
                s.pop();
            }
            // 每个数字都要进一次栈
            s.push(sequence[i]);
        }
        return true;
    }
};

Python实现代码：

class Solution:
    def VerifySquenceOfBST(self , sequence: List[int]) -> bool:
        # 特殊情况处理
        if not sequence: return False
        # 初始化
        s, root = [], 999999
        # 倒序遍历
        for i in range(len(sequence) -1, -1, -1):
            # 存在左子树大于父节点root的情况，违背二叉搜索树性质
            if sequence[i] > root: return False;
            # 找当前遍历节点的父节点
            while s and sequence[i] < s[-1]:
                root = s.pop()
            s.append(sequence[i])
        return True

复杂度分析：

• 时间复杂度：$O(n)O(n)$，$nn$代表sequence长度，各个节点均入栈、 出栈一次，因此时间代价和序列长度呈线性关系
• 空间复杂度：$O(n)O(n)$，最差情况下单调栈存储所有节点，使用$O(n)O(n)$空间

方法二：（扩展思路）

知识点：二叉树递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。

思路：

递归函数的参数包含三个信息：遍历序列，树的起点索引位置，树的重点索引位置。

对于后序遍历的二叉搜索树来讲，终点位置就是根，然后从后往前遍历找到的第一个小于终点位置的节点，就是在序列中划分左右子树的分割位置。

只要能够一直划分下去，直到递归最后是单个节点，则说明应该返回true，否则返回false

具体做法：

• step 1：首先对于给定列表长度为0的特殊情况返回false
• step 2：递归函数中返回条件为 l>=r，返回true
• step 3：递归函数中确定根节点为sequence[r]，然后从后往前遍历找到左右子树分割点，进行继续递归

Java实现代码：

import java.util.*;
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0) return false;
        return order(sequence, 0, sequence.length - 1);
    }
    
    public boolean order(int [] sequence, int l, int r) {
        // 剩一个节点的时候 返回 true
        if(l >= r) return true;
        int j;
        int mid = sequence[r];
        
        // 找到左子树和右子树的分界点，j代表左子树的最后一个索引位置
        for(j = r; j >= l; j--) {
            int cur = sequence[j];
            if(cur < mid) break;
        }
        
        // 判断所谓的左子树中是否又不合法（不符合二叉搜索树）的元素
        for(int i = j; i >= l; i--) {
            int cur = sequence[i];
            if(cur > mid) return false;
        }
        return order(sequence, l, j) && order(sequence, j+1, r-1);
    }
}

C++实现代码：

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size() == 0) return false;
        return order(sequence, 0, sequence.size() - 1);
    }
    bool order(vector<int>& sequence, int l, int r) {
        // 剩一个节点的时候 返回 true
        if(l >= r) return true;
        int j;
        int mid = sequence[r];
        
        // 找到左子树和右子树的分界点，j代表左子树的最后一个索引位置
        for(j = r; j >= l; j--) {
            int cur = sequence[j];
            if(cur < mid) break;
        }
        
        // 判断所谓的左子树中是否又不合法（不符合二叉搜索树）的元素
        for(int i = j; i >= l; i--) {
            int cur = sequence[i];
            if(cur > mid) return false;
        }
        return order(sequence, l, j) && order(sequence, j+1, r-1);
    }
};

Python实现代码：

class Solution:
    def VerifySquenceOfBST(self , sequence: List[int]) -> bool:
        if not len(sequence): return False
        def order(l, r):
            if l >= r: return True
            # i 从边界l开始先遍历所有小于根节点的数字
            i = l
            while sequence[i] < sequence[r]: i += 1
            # i 继续遍历所有大于根节点的数字
            j = i
            while sequence[i] > sequence[r]: i += 1
            # 判断是否i到达了此范围内的边界重点r，并继续递归
            return i == r and order(l, j-1) and order(j, r-1)
        return order(0, len(sequence) - 1)

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，递归操作每次排除掉一个根节点，因此递归次数是$O(n)O(n)$，而最差情况下树退化成链表，每次递归内又要遍历所有节点，还是$O(n)O(n)$，因此最终代价就是$O(n^2)O(n^2)$
• 空间复杂度：$O(n)O(n)$，最差情况下树退化成链表，递归深度就是$O(n)O(n)$