米鼠商城

多快好省,买软件就上米鼠网

最新项目

人才服务

靠谱的IT人才垂直招聘平台

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

  • lkj155
  • 2
  • 2020-05-23 08:25

我的LeetCode:https://leetcode-cn.com/u/ituring/

我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii

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

题目

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

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

     5
    / \
   2   6
  / \
 1   3

示例 1:

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

示例 2:

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

提示:

  • 数组长度 <= 1000

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

思路1-分治递归

后序遍历:left->right->root; 因此,数组的最后一个元素是根节点,而数组的前一部分是左子树,后一部分是右子树; 那么,根据搜索二叉树的特性,左子树都小于根节点,右子树都大于根节点,依此校验即可; 以上述左右子树的分割点可将数组分为两部分,然后各自递归校验;

算法复杂度:

  • 时间复杂度: $ {\color{Magenta}{\Omicron\left(n^{2}\right)}} $
  • 空间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $ 递归栈的深度

思路2-使用辅助单调栈

后序遍历:left->right->root; 考虑对数组倒序遍历,那么节点的情况就变为:root->right->left; root为根,然后是右子树,左子树,那么以root作为栈底,逆序先处理的是右子树节点,均大于root值,按序入栈; 当遇到小于栈顶元素的值时,表明右子树已经全入栈了,那么此时可以清空栈,开始对左子树的递归处理,且根元素更新为左子树的根;

算法复杂度:

  • 时间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
  • 空间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $

算法源码示例

package leetcode;

import java.util.Stack;

/**
 * @author ZhouJie
 * @date 2020年5月22日 下午6:31:34 
 * @Description: 面试题33. 二叉搜索树的后序遍历序列
 *
 */
public class LeetCode_Offer_33 {

}

class Solution_Offer_33 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年5月22日 下午6:32:04 
	 * @param: @param postorder
	 * @param: @return
	 * @return: boolean
	 * @Description: 1-后序遍历:left->right->root;
	 * 				数组最后一个元素是根元素,数组靠前一段是左子树,靠后一段是右子树;
	 * 				二叉搜索树的特性,根元素大于左子树小于右子树,以此校验;
	 * 				初始的左右子树分割后的部分也符合校验模式,故可递归校验处理;
	 *
	 */
	public boolean verifyPostorder_1(int[] postorder) {
		return verifyHelper(postorder, 0, postorder.length - 1);
	}

	private boolean verifyHelper(int[] postorder, int start, int end) {
		if (start >= end) {
			return true;
		} else {
			int i = start;
			// 左子树都小于根节点
			while (i < end && postorder[i] < postorder[end]) {
				i++;
			}
			int j = i;
			// 右子树都大于根节点,一旦小于则直接返回
			while (j < end) {
				if (postorder[j] < postorder[end]) {
					return false;
				}
				j++;
			}
			// 以i分割左右子树递归校验
			return verifyHelper(postorder, start, i - 1) && verifyHelper(postorder, i, end - 1);
		}
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年5月22日 下午7:18:15 
	 * @param: @param postorder
	 * @param: @return
	 * @return: boolean
	 * @Description: 2-单调辅助栈校验;
	 * 				后序遍历:left->right->root;
	 * 				若对数组逆序遍历,则对应节点顺序为:root->right->left;
	 * 				root作为栈最底的元素,先校验右子树都大于root的部分,当遇到小于栈顶的元素时,表明到了左子树,此时清空栈开始处理左子树;
	 *
	 */
	public boolean verifyPostorder_(int[] postorder) {
		Stack<Integer> stack = new Stack<Integer>();
		// 初始化根节点
		int root = Integer.MAX_VALUE;
		for (int i = postorder.length - 1; i > -1; i--) {
			// 若左子树中有大于根节点的值,直接返回false
			if (postorder[i] > root) {
				return false;
			}
			// 若当前值小于栈顶的值,说明右子树已经遍历完毕,栈中都是右子树,清空栈,但记录根元素,然后左子树入栈
			while (!stack.isEmpty() && postorder[i] < stack.peek()) {
				root = stack.pop();
			}
			// 若栈为空是右子树入栈,否则为左子树入栈
			stack.push(postorder[i]);
		}
		return true;
	}

}



这里给大家推荐一个在线软件复杂项交易平台:米鼠网 https://www.misuland.com

米鼠网自成立以来一直专注于从事软件项目人才招聘软件商城等,始终秉承“专业的服务,易用的产品”的经营理念,以“提供高品质的服务、满足客户的需求、携手共创双赢”为企业目标,为中国境内企业提供国际化、专业化、个性化、的软件项目解决方案,我司拥有一流的项目经理团队,具备过硬的软件项目设计和实施能力,为全国不同行业客户提供优质的产品和服务,得到了客户的广泛赞誉。

猜你喜欢

评论留言