题解 | #二叉搜索树的后序遍历序列#
二叉搜索树的后序遍历序列
https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd
#include <stack> 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 = l; j <r; j++) { int cur = sequence[j]; if(cur > mid) break; } // 判断所谓的左子树中是否又不合法(不符合二叉搜索树)的元素 for(int i = j; i < r; i++) { int cur = sequence[i]; if(cur < mid) return false; } return order(sequence, l, j-1) && order(sequence, j, r-1); } };
使用递归的思路,首先判断当前根节点下是否满足二叉搜索树(左子树的值都小于根节点,右子树的值都大于根节点),然后找到左右子树分界点,递归对左右子树进行判断是否满足二叉搜索树
注意:后续遍历末尾的值就是整棵树的根节点