死磕算法系列文章
“Leetcode : https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof
“GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_26_verifyPostorder/Solution.java
题目描述 :输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true
,否则返回 false
。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树:
5
/ \
2 6
/ \
1 3
示例 1:
输入: [1,6,3,2,5]
输出: false
示例 2:
输入: [1,3,2,6,5]
输出: true
解题思路:
[ 左子树 | 右子树 | 根节点 ]
,即遍历顺序为 “左、右、根” 。复杂度分析:
package com.nateshao.sword_offer.topic_26_verifyPostorder;
import java.util.Stack;
/**
* @date Created by 邵桐杰 on 2021/11/30 14:22
* @微信公众号 程序员千羽
* @个人网站 www.nateshao.cn
* @博客 https://nateshao.gitee.io
* @GitHub https://github.com/nateshao
* @Gitee https://gitee.com/nateshao
* Description:
*/
public class Solution {
public static void main(String[] args) {
int[] postorder = {1, 3, 2, 6, 5};
int[] postorder2 = {1, 6, 3, 2, 5};// false
int[] postorder3 = {1, 6, 3, 2, 5};// false
System.out.println("递归:(postorder) = " + verifyPostorder(postorder));
System.out.println("递归:(postorder2) = " + verifyPostorder(postorder2));
}
public static boolean verifyPostorder(int[] postorder) {
return recur(postorder, 0, postorder.length - 1);
}
public static boolean recur(int[] postorder, int i, int j) {
if (i >= j) return true;
int p = i;
while (postorder[p] < postorder[j]) p++;
int m = p;
while (postorder[p] > postorder[j]) p++;
return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
}
/**
* 递归:(postorder) = true
* 递归:(postorder2) = false
*/
}
后序遍历 倒序: [ 根节点 | 右子树 | 左子树 ]
。类似 先序遍历的镜像 ,即先序遍历为 “根、左、右” 的顺序,而后序遍历的倒序为 “根、右、左” 顺序。
算法流程:
package com.nateshao.sword_offer.topic_26_verifyPostorder;
import java.util.Stack;
/**
* @date Created by 邵桐杰 on 2021/11/30 14:22
* @微信公众号 程序员千羽
* @个人网站 www.nateshao.cn
* @博客 https://nateshao.gitee.io
* @GitHub https://github.com/nateshao
* @Gitee https://gitee.com/nateshao
* Description: 二叉搜索树的后序遍历序列
*/
public class Solution {
public static void main(String[] args) {
int[] postorder3 = {1, 6, 3, 2, 5};// false
System.out.println("栈:(postorder3) = " + verifyPostorder2(postorder3));
}
/**
* 方法二:栈
*
* @param postorder
* @return
*/
public static boolean verifyPostorder2(int[] postorder) {
Stack<Integer> stack = new Stack<>();
//初始化: 单调栈 stackstack ,父节点值 root = +∞ (初始值为正无穷大,可把树的根节点看为此无穷大节点的左孩子);
int root = Integer.MAX_VALUE;
// 倒序遍历 postorder:记每个节点为 i
for (int i = postorder.length - 1; i >= 0; i--) {
// 若 ri>root,说明此后序遍历序列不满足二叉搜索树定义,直接返回 false ;
if (postorder[i] > root) return false;
// 更新父节点root:当栈不为空且 stack.peek()>ri时,循环执行出栈,并将出栈节点赋给 root
while (!stack.isEmpty() && stack.peek() > postorder[i])
root = stack.pop();
stack.add(postorder[i]); // 入栈: 将当前节点 ri
}
return true; //遍历完成,则说明后序遍历满足二叉搜索树定义,返回 true 。
}
/**
* 递归:(postorder) = true
* 递归:(postorder2) = false
* 栈:(postorder3) = false
*/
}
参考链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/solution/mian-shi-ti-33-er-cha-sou-suo-shu-de-hou-xu-bian-6