安监网站安全建设信息,ps教程app,怎么安装wordpress主题,网站开发项目付款方式本题主要在于考察对二叉搜索树和后序遍历的理解。原题输入一个整数数组#xff0c;判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true#xff0c;否则返回 false。假设输入的数组的任意两个数字都互不相同。参考以下这颗二叉搜索树#xff1a;5 / 2 6…本题主要在于考察对二叉搜索树和后序遍历的理解。原题输入一个整数数组判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true否则返回 false。假设输入的数组的任意两个数字都互不相同。参考以下这颗二叉搜索树 5 / 2 6 / 1 3示例 1输入: [1,6,3,2,5]输出: false示例 2输入: [1,3,2,6,5]输出: true提示数组长度 1000原题urlhttps://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/解题基本概念首先介绍一些基本概念方便后续做题。后序遍历[ 左子树 | 右子树 | 根节点 ] 即遍历顺序为 “左、右、根” 。二叉搜索树 左子树中所有节点的值 根节点的值右子树中所有节点的值 根节点的值其左、右子树也分别为二叉搜索树。递归分治既然本题只提供了后序遍历那么我们就要在此基础之上下功夫了。根据上面的提供的说明后序遍历是先左右子树再根节点那么根是容易判断的肯定在整个序列的最后。而二叉搜索树节点值满足左子树 根 右子树因此我们就可以以根为基础从后向前遍历。一开始的节点肯定都大于根因为都在右子树上一旦出现小于根的节点说明就进入了左子树那么之后所有的节点都应该小于根。然后再分别遍历左右子树直至到叶子节点为止(即无左右子树的节点)。按照上面的方法就需要我们将后序遍历分成左右子树不断递归遍历检查。接下来看看代码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 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 存储所有节点。神奇的是力扣给出的执行结果显示递归分治方法消耗的时间更短。这点大家也可以研究研究是为什么。总结以上就是这道题目我的解答过程了不知道大家是否理解了。本题主要在于考察对二叉搜索树和后序遍历的理解递归分治是容易想出来的方法但是后面那种单调递增栈确实很难想到可以作为一种特殊思路进行理解。有兴趣的话可以访问我的博客或者关注我的公众号、头条号说不定会有意外的惊喜。https://death00.github.io/公众号健程之道
