面试题33:二叉搜索树的后序遍历序列

    xiaoxiao2025-05-03  28

    二叉搜索树的后序遍历序列

    题目描述

    题目描述

    输入一个整数数组,判断该数组是否是某个二叉搜索树的后序遍历结果

    eg. {5,7,6,9,11,10,8} 8为根节点,将数组分成两部分,左部分都小于8, 右部分都大于8。每部分最后一个节点为根节点,依次判断。

    bool VerifySquenceOfBST(int sequence[], int length) { if(sequence == nullptr || length <=0) return false; int root = sequence[length-1]; int i =0; for(; i<length-1; i++) { if(sequence[i] >root) break; } int j=i; for(; j<length-1; j++) { if(sequence[j] <root) return false; } bool left = true; if(i>0) left = VerifySquenceOfBST(sequence, i); bool right = true; if(i<length-1) right = VerigySquenceOfBST(sequence+i, length-i-1); return left && right; }
    最新回复(0)