专栏首页健程之道剑指offer 33——二叉搜索树的后序遍历序列

剑指offer 33——二叉搜索树的后序遍历序列

本题主要在于考察对二叉搜索树和后序遍历的理解。

原题

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树:

     5
    / \
   2   6
  / \
 1   3

示例 1:

输入: [1,6,3,2,5]
输出: false

示例 2:

输入: [1,3,2,6,5]
输出: true

提示:

  • 数组长度 <= 1000

原题url:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/

解题

基本概念

首先介绍一些基本概念,方便后续做题。

  1. 后序遍历:[ 左子树 | 右子树 | 根节点 ] ,即遍历顺序为 “左、右、根” 。
  2. 二叉搜索树:左子树中所有节点的值 < 根节点的值;右子树中所有节点的值 > 根节点的值;其左、右子树也分别为二叉搜索树。

递归分治

既然本题只提供了后序遍历,那么我们就要在此基础之上下功夫了。

根据上面的提供的说明,后序遍历是,先左右子树再根节点,那么根是容易判断的,肯定在整个序列的最后。

而二叉搜索树节点值满足,左子树 < 根 < 右子树,因此我们就可以以根为基础,从后向前遍历,。

一开始的节点肯定都大于根,因为都在右子树上,一旦出现小于根的节点,说明就进入了左子树,那么之后所有的节点都应该小于根。然后再分别遍历左右子树,直至到叶子节点为止(即无左右子树的节点)。

按照上面的方法,就需要我们将后序遍历分成左右子树,不断递归遍历检查。

接下来看看代码:

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

    private boolean checkTree(int[] postorder, int start, int end) {
        // 如果start >= end,说明已经寻找结束
        if (start >= end) {
            return true;
        }

        // 找到根
        int root = postorder[end];
        // 左子树开始的下标
        int leftStart = start;
        // 左子树结束的下标
        int leftEnd = leftStart;
                // 找到第一个大于根节点的值
        while (leftEnd < end && postorder[leftEnd] < root) {
            leftEnd++;
        }
        leftEnd--;

        // 右子树开始的下标
        int rightStart = leftEnd + 1;
        // 右子树结束的下标
        int rightEnd = end - 1;
        // 检查右子树是否都大于根节点
        for (int i = rightStart; i < end; i++) {
            if (postorder[i] > root) {
                continue;
            }

            return false;
        }

        // 继续检查左右子树
        return checkTree(postorder, leftStart, leftEnd) &&
                checkTree(postorder, rightStart, rightEnd);
    }
}

提交OK。

分析一下复杂度:

  • 时间复杂度 O(N^2) :每次调用 checkTree 方法减去一个根节点,因此递归占用 O(N) ;最差情况下(即当树退化为链表),每轮递归都需遍历树所有节点,占用 O(N ^ 2) 。
  • 空间复杂度 O(N) :最差情况下(即当树退化为链表),递归深度将达到 N 。

递增栈

既然上面分析出时间复杂度为 O(N^2) ,那么是否可以找到一种更高效的方法,只遍历一次序列,就可以解决问题呢?因为这样可以在时间复杂度上进行很大的优化。

这就需要再进一步结合搜索二叉树和后序遍历的特性了。(这个方法我是在网上看到的,感觉属于一种比较偏门的优化,一般很难想出这种方法)

在我们从后向前遍历序列时,大致是经历了根、右子树、左子树,而左子树 < 根 < 右子树,那么一开始应该是单调递增的,我们可以将这些节点依次入栈。

当不满足单调递增调试时,一般是碰到了右子树中某一个左子树节点,或者真正的左子树,这时候可以将栈顶元素出栈,直到碰到比当前节点小的元素,那么将最后的栈顶元素设为根节点

此时继续遍历,应该保证所有节点都小于根节点,因为此时已经进入左子树序列了。否则说明该序列不满足搜索二叉树的后序遍历。

重复以上步骤,如果遍历结束,说明满足搜索二叉树的后序遍历。

这么说可能比较难懂,直接上代码:

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        // 单调递增栈
        Stack<Integer> stack = new Stack<>();
        int root = Integer.MAX_VALUE;
        // 倒序遍历
        for (int i = postorder.length - 1; i >= 0; i--) {
            if (postorder[i] > root) {
                return false;
            }
            // 如果当前栈不为空,且当前遍历的节点小于栈顶节点
            while (!stack.isEmpty() &&
                postorder[i] < stack.peek()) {
                // 栈顶节点压出,且更新根节点
                root = stack.pop();
            }
            // 当前节点入栈
            stack.push(postorder[i]);
        }
        return true;
    }
}

提交OK。

分析一下复杂度:

  • 时间复杂度 O(N) :遍历 postorder 所有节点,各节点均入栈 / 出栈一次,使用 O(N) 时间。
  • 空间复杂度 O(N) :最差情况下(即当树退化为链表),单调递增栈 stack 存储所有节点。

神奇的是,力扣给出的执行结果显示:递归分治方法消耗的时间更短。这点大家也可以研究研究是为什么。

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。本题主要在于考察对二叉搜索树和后序遍历的理解,递归分治是容易想出来的方法,但是后面那种单调递增栈确实很难想到,可以作为一种特殊思路进行理解。

本文分享自微信公众号 - 健程之道(JianJianCoder),作者:健健壮

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 力扣213——打家劫舍 II

    你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有...

    健程之道
  • 剑指offer 13——机器人的运动范围

    地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(...

    健程之道
  • 力扣105——从前序与中序遍历序列构造二叉树

    原题url:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-i...

    健程之道
  • Leetcode: Construct Binary Tree from Inorder and Postorder Traversal

    题目: Given inorder and postorder traversal of a tree, construct the binary tree...

    卡尔曼和玻尔兹曼谁曼
  • 【图解数据结构】 一组动画彻底理解二叉树遍历

    定义:二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。

    五分钟学算法
  • Day 4:重建二叉树

    思路1: 背景知识介绍:   首先我们应该了解的是:   前序遍历的顺序是:根——左结点——右结点   中序遍历的顺序是:左结点——根——右结点   ...

    stefan666
  • leetcode:104二叉树的最大深度

    思路:用深度优先遍历。 深度优先遍历是尽可能深的遍历这棵树。 怎么做? 新建一个变量记录每一个节点的层级,找到最大的层级即可。

    用户7873631
  • 前序遍历中序遍历求后序遍历-数组篇

    如果已知前序遍历和中序遍历,那么肯定能够求出后序遍历。正常的思路就是,根据前序遍历和中序遍历,我们把二叉树的结构给描述出来,然后再使用后序遍历。

    chain
  • L2-006. 树的遍历

    给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

    指点
  • 剑指offer第5题:重建二叉树

    这道题要求我们根据中序遍历和前序遍历构建一颗二叉树。在前序遍历中,遍历顺序为根节点-->左节点-->右节点,中序遍历顺序为左节点-->根节点-->右节点,所以我...

    鹏-程-万-里

扫码关注云+社区

领取腾讯云代金券