【二叉树专题】剑指 Offer 33. 二叉搜索树的后序遍历序列-跟着帅地玩副业，开拓第二曲线PlayOffer

Miracle· 普通 2023年9月7日下午6:55

class Solution {
public:
// 递归
bool travel(vector &postorder, int start, int end) {
if (start >= end) return true;
int index = start;
// 寻找第一个大于根节点的值,即找到根节点的右孩子
while (postorder[index] < postorder[end]) index++;
int midindex = index; // 右子树的索引位置
while (postorder[index] > postorder[end]) index++;//将索引走到不大于end的位置,
// 递归左右子树
bool left = travel(postorder, start, midindex – 1);
bool right = travel(postorder, midindex, end – 1);
// 如果index能成功到end的位置,认为这是一个搜索二叉树的后序遍历
return index end && left && right;
}

bool verifyPostorder(vector<int>& postorder) {
    return travel(postorder, 0, postorder.size() - 1);
}

};

0 赞同 0 条回复

Sheng 永久会员 2023年8月29日上午12:48

二叉树的后序遍历是中右左为遍历顺序的倒序，根据这种方法分离出根节点，左子树右子树。根据搜索树的性质，左子树节点小于根节点，右子树大于，判断是否为true

    public boolean verifyPostorder(int[] postorder) {
        if(postorder == null || postorder.length == 0) return true;
        int len = postorder.length;
        int[] preorder = new int[len];
        for(int i=0; i<len; i++) {
            preorder[len-i-1] = postorder[i];
        }

        return f(arr, 0, len-1);
    }

    public boolean f(int[] preorder, int begin, int end) {
        if(begin >= end) return true;

        int left = -1;
        int j = 0;
        if(preorder[begin+1] < preorder[begin]) {
            //开始就是左子树
            left = begin + 1;
            for(j=left; j<=end; j++) {
                if(preorder[j] > preorder[begin]) {
                    return false;//左子树中不能含有大于根节点begin的节点
                }
            }
            return f(preorder, left, end);//left以后全是左子树
        }
        else {
            //开始是右子树
            int right = begin + 1;
            left = -1;
            for(j = right; j <= end; j++) {
                if(preorder[j] < preorder[begin]) {
                    left = j;//左子树根节点
                    break;
                }
            }
            if(left != -1) {
                for(; j<=end; j++) {
                    if(preorder[j] > preorder[begin]) {
                        return false;//左子树中不能包含大于根节点begin的节点
                    }
                }
                return f(preorder, right, left-1) && f(preorder, left, end);//右子树 && 左子树
            }
            else {
                return f(preorder, right, end);//right以后全是右子树
            }
        }
    }

0 赞同 0 条回复

小肸永久会员 2023年8月28日下午4:04

class Solution {
    //递归写法，树退化成链表时，时间复杂度O(N^2)，空间复杂度O(N)。
    //可以使用单调栈。后序遍历为左 | 右 | 中。而后序遍历的倒序为中 | 右 | 左，所以中 | 右这是递增的，左是递减的
    public boolean verifyPostorder(int[] postorder) {
        return verifyPostorderCore(postorder, 0, postorder.length - 1);
    }
    boolean verifyPostorderCore(int[] postorder, int left, int right) {
        if (left >= right) {
            return true;
        }
        int rootVal = postorder[right];
        int rightIndex = right;
        while (rightIndex >= left && postorder[rightIndex] >= rootVal) {
            rightIndex --;
        }
        int index = rightIndex;
        while (rightIndex >= left && postorder[rightIndex] < rootVal) {
            rightIndex --;
        }
        if (rightIndex >= left) {
            return false;
        } else {
            return verifyPostorderCore(postorder, left, index) && verifyPostorderCore(postorder, index + 1, right - 1);
        }
    }
}

0 赞同 0 条回复

sincere 普通 2023年8月27日下午10:05

思路：二叉搜索树的后序遍历中，最后一个是根节点，并且二叉搜索树左子树都小于根，右子树都大于根，所以遍历可以找到左右子树的范围，然后递归遍历左右子树
复杂度：时间复杂度O(n2)，空间复杂度O(n)

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return build(postorder, 0, postorder.length - 1);
    }

    public boolean build(int[] postorder, int start, int end) {
        if (start >= end) {
            return true;
        }
        int tmp = start;
        while (postorder[tmp] < postorder[end]) {
            tmp++;
        }
        int mid = tmp;
        while (postorder[tmp] > postorder[end]) {
            tmp++;
        }
        return (tmp == end) && build(postorder, start, mid - 1) && build(postorder, mid, end - 1);
    }
}

0 赞同 0 条回复

sc_Yang 普通 2023年8月27日下午6:10

单独拎出个函数递归

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        if(postorder.size()==0){
            return true;
        }
        return verify(postorder, 0, postorder.size()-1);
    }
    bool verify(vector<int>& postorder, int fir, int lst){
        if(fir>=lst) return true;
        int flag = lst-1;
        // 从前往后数选出第一个大于partition的元素，并且把flag置到那个位置
        while(flag>=fir && postorder[flag]>postorder[lst]){
            flag--;
        }
        for(int i=flag-1; i>=fir; i--){
            if(postorder[i]>postorder[lst]){
                return false;
            }
        }
        return verify(postorder,fir, flag) && verify(postorder,flag+1, lst-1);
    }
};

0 赞同 0 条回复

c 普通 2023年8月23日下午9:58

递归

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return fun(postorder,0,postorder.length-1);
    }
    public boolean fun(int[] postorder,int left,int right){
        if(left==right || left+1==right || right+1==left){
            return true;
        }
        int max = postorder[right];
        int index=-1;
        for(int i = left;i<=right-1;i++){
            if(index!=-1){
                if(postorder[i]<max){
                    return false;
                }
            }else{
                if(postorder[i]>max){
                    index=i;
                }
            }
        }
        if(index==-1){
            index=right;
        }
        return fun(postorder,left,index-1) && fun(postorder,index,right-1);
    }
}

0 赞同 0 条回复

帝心引力永久会员 2023年8月23日下午9:50

时间o(n), 空间o(n)
class Solution {
public:
    bool ans = true;
    bool verifyPostorder(vector<int>& postorder) {
        // 后序遍历：左 右 根
        // 最后一个元素为根
        // 遍历数组，第一个比根大的元素为右子树的最小的结点
        // 从这个结点开始往后遍历，如果有比根节点值小的 则不满足题目
        dfs(postorder, 0, postorder.size()-1);
        return ans;
    }
    void dfs(vector<int>& postorder, int l, int r){
        if(l > r || ans==false) return;
        int root_val = postorder[r];
        int i,k;
        for(i=l; i<r && postorder[i]<root_val; i++);
        for(k=i+1;k<r;k++){
            if(postorder[k] < root_val) ans = false;
        }
        dfs(postorder, l, i-1);
        dfs(postorder, i, r-1);
    }
};

0 赞同 0 条回复

JustRtn 普通 2023年8月21日下午10:01

后续遍历序列从第一个大于根节点（序列尾）的开始，后面的都应该大于根节点（右子树）

class Solution {
public:
    bool f(vector<int>& postorder, int left, int right) {
        if (left >= right) {
            return true;
        }
        int mid = left;
        while (postorder[mid] < postorder[right]) mid++;
        for (int i = mid; i < right; i++) {
            if (postorder[i] < postorder[right]) {
                return false;
            }
        }
        return f(postorder, left, mid-1) && f(postorder, mid, right - 1);
    }

    bool verifyPostorder(vector<int>& postorder) {
        return f(postorder, 0, postorder.size() -1);
    }
};

0 赞同 0 条回复

行动派小彩笔普通 2023年8月21日下午9:56

 //时间复杂度最坏O(n^2)
// 空间复杂度最坏O(n)
class Solution {
public:
    bool verify(vector& postorder,int left,int right)
    {
        if(left>=right) return true;
        int root = postorder[right];
        int pos = right-1;
        while((root& postorder) {
        if(postorder.size()<=1) return true;
        return verify(postorder,0,postorder.size()-1);
    }
};

0 赞同 0 条回复

别扒拉我普通 2023年8月21日下午9:27

1、递归

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0 || inorder.length == 0){
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        int len = preorder.length;
        for(int i=0; i<len; i++){
            if(inorder[i] == preorder[0]){
                root.left = buildTree(Arrays.copyOfRange(preorder, 1, i+1), Arrays.copyOfRange(inorder, 0, i));
                root.right = buildTree(Arrays.copyOfRange(preorder, i+1, len), Arrays.copyOfRange(inorder, i+1, len));
            }
        }
        return root;
    }
}

0 赞同 0 条回复

塔底的仰望永久会员 2023年8月21日下午5:26

时间复杂度O(n); 空间复杂度O(n)

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length == 0 
            || inorder.length == 0) {
            return null;
        }

        return build(preorder, inorder, 0, preorder.length -1, 0, inorder.length -1);

    }

    public TreeNode build(int[] preorder, int[] inorder, int pl, int pr, int il, int ir) {
        if (pl > pr || il > ir) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[pl]);
        int tag = -1;
        for(int i = il; i <= ir; i++) {
            if (inorder[i] == root.val) {
                tag = i;
                break;
            }
        }
        root.left = build(preorder, inorder, pl + 1, pl + tag - il, il, tag -1);
        root.right = build(preorder, inorder, pl + tag -il + 1, pr, tag + 1, ir);
        return root;
    }
}

0 赞同 0 条回复

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

共以下 11 个回答

# 回答此问题取消回复

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

共以下 11 个回答

# 回答此问题 取消回复

# 回答此问题取消回复