首页 > 其他分享 >剑指 Offer 33. 二叉搜索树的后序遍历序列

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

时间:2023-04-08 23:35:03浏览次数:53  
标签:子树 Offer 33 二叉 leftchild 遍历 序列 节点 postorder

题目链接:剑指 Offer 33. 二叉搜索树的后序遍历序列

方法:分治

解题思路

  1. 首先假设该序列能够构成某个二叉搜索树的后序遍历序列,那么这个序列会被分成3个部分:左子树序列,右子树序列,父节点,其中左右子树节点数可能为0;
  2. 现在就可以检查该序列是否符合这个规律,然后递归的判断子树是否符合规律。
    • 当序列的大小(即树的大小) \(<= 3\) 时,该序列一定可以构成二叉搜索树的后序遍历序列;
    • 从右向左找到第一个小于父节点的值的下标,那么从该下标到序列起点的部分为左子树序列,此时判断左子树序列中是否全部小于父节点的值,一旦有一个不符合则返回false;然后若左右子树存在,则继续检查其对应子树。

代码

class Solution {
public:
    bool check(vector<int>& postorder, int l, int r) {
        if (r - l <= 2) return true;
        int leftchild = r;
        bool flag = true;
        while (leftchild >= l) { // 从右向左找到第一个小于父节点的值的下标
            if (postorder[leftchild] >= postorder[r]) leftchild -- ;
            else break;
        }
        if (leftchild != l - 1) {
            int idx = leftchild;
            while (idx >= l) { // 一旦有一个 >= root,则返回false
                if (postorder[idx] >= postorder[r]) return false;
                idx -- ;
            }
            flag &= check(postorder, l, leftchild); // 检查其对应子树
        } 
        if (leftchild != r - 1) {
            flag &= check(postorder, leftchild + 1, r - 1); // 检查其对应子树
        }
        return flag;
    }
    bool verifyPostorder(vector<int>& postorder) {
        int n = postorder.size();
        return check(postorder, 0, n - 1);
    }
};

复杂度分析

时间复杂度:\(O(n^2)\),最坏情况退化为链表,每轮遍历当前所有节点;
空间复杂度:\(O(n)\),调用栈空间,最坏情况为高度为n;

标签:子树,Offer,33,二叉,leftchild,遍历,序列,节点,postorder
From: https://www.cnblogs.com/lxycoding/p/17299572.html

相关文章

  • 108. 将有序数组转换为二叉搜索树
    题目链接:108.将有序数组转换为二叉搜索树方法:递归建树解题思路每次选取中间的元素作为根节点,递归创建左右子树,就可以保证左右子树的高度差绝对值不超过1代码/***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*......
  • 剑指 Offer 20. 表示数值的字符串
    题目链接:剑指Offer20.表示数值的字符串方法:模拟解题思路根据题意模拟,详情见代码注释。代码classSolution{public:boolisDecimal(strings){intfirst_symbol=s.find_first_of('.');//第一个'.'的位置intlast_symbol=s.find_last_of('.'......
  • misc | 解决windows cmd不能正确显示\033彩色字符
    misc|解决windowscmd不能正确显示\033彩色字符今天重装winpwn结果显示的是乱码,很影响,搜了一下发现可以安装一个工具来解决。参考:https://www.cnblogs.com/naiij/p/9772584.html工具:https://github.com/adoxa/ansicon/releases......
  • COMP3311 PostgreSQL 数据库写法
    COMP331123T1Assignment2Python,PostgreSQL,psycopg2DatabaseSystemsLastupdated:Thursday6thApril9:06amMostrecentchangesareshowninred...olderchangesareshowninbrown.[AssignmentSpec][DatabaseDesign][Examples][Testing][Submitting][F......
  • 剑指 Offer 19. 正则表达式匹配
    题目链接:剑指Offer19.正则表达式匹配方法:动态规划解题思路详情见:逐行详细讲解,由浅入深,dp和递归两种思路代码classSolution{public:boolisMatch(strings,stringp){intn=s.size(),m=p.size();boolf[n+1][m+1];//f[i][j]代表s......
  • poj-3367(线段树+区间合并)
    HotelPOJ-3667思路:与hdu-1540(线段树+区间合并)-魏老6-博客园(cnblogs.com)类似,只不过是区间修改,多维护一个最大连续区间sum。#define_CRT_SECURE_NO_WARNINGS1#include<algorithm>#include<fstream>#include<iostream>#include<cstdio>#include<deque>#includ......
  • Leetcode(剑指offer专项训练)——DFS/BFS专项(1)
    计算除法题目给定一个变量对数组equations和一个实数值数组values作为已知条件,其中equations[i]=[Ai,Bi]和values[i]共同表示等式Ai/Bi=values[i]。每个Ai或Bi是一个表示单个变量的字符串。另有一些以数组queries表示的问题,其中queries[j]=[Cj,Dj]......
  • 剑指offer66(Java)-构建乘积数组(中等)
    题目:给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中 B[i]的值是数组A中除了下标i以外的元素的积,即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。 示例:输入:[1,2,3,4,5]输出:[120,60,40,30,24] 提示:所有元素乘积之和不会......
  • 剑指offer03(Java)-数组中重复的数字(简单)
    题目:找出数组中重复的数字。在一个长度为n的数组nums里的所有数字都在0~n-1的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。示例1:输入:[2,3,1,0,2,5,3]输出:2或3 限制:2<=n<=1000......
  • JZ8 二叉树的下一个结点
    做法一:直接求出中序遍历,并用vector容器存储。/*structTreeLinkNode{intval;structTreeLinkNode*left;structTreeLinkNode*right;structTreeLinkNode*next;TreeLinkNode(intx):val(x),left(NULL),right(NULL),next(NULL){......