吉林市网站建设,促销式软文案例,为什么做美妆网站,网页开发和app开发哪个难描述
剑指offer JZ33 二叉搜索树的后序遍历序列 输入一个整数数组#xff0c;判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。 数据范围#xff1a; 节点数量 0≤n≤1000 #xff0c;节点上…描述
剑指offer JZ33 二叉搜索树的后序遍历序列 输入一个整数数组判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。 数据范围 节点数量 0≤n≤1000 节点上的值满足 1≤val≤105保证节点上的值各不相同 提示 1.二叉搜索树是指父亲节点大于左子树中的全部节点但是小于右子树中的全部节点的树。 2.该题我们约定空树不是二叉搜索树 3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历
方法逆序遍历栈
思路 后序遍历的顺序是左子树 — 右子树 — 根节点。那么其逆序便为根节点 — 右子树 — 左子树。我们逆序遍历如果是后一个节点大于前一个节点说明后一个节点是前一个节点的右节点。并且我们每遍历一个节点就将其压入栈中。当我们发现后一个节点小于前一个节点说明前一个节点没有右节点了并且后一个节点是前一个节点或者前一个节点的父节点的左节点那么我们就通过栈找到后一个节点的父节点并且以后的节点都只能比这个节点小。 具体实现及注释
import java.util.*;
public class Solution {public boolean VerifySquenceOfBST(int [] sequence) {int length sequence.length;//空树不是二叉搜索树if (length 0) return false;//实例化栈DequeInteger stack new ArrayDeque();//初始化根节点因为树中最大值为100000所以初始化一个最大虚拟值相当于把原树的根节点作为此虚拟节点的左节点。int rootValue 100001;for (int i length-1; i 0; i--) {int curValue sequence[i];//因为rootValue存的是根节点的值而curValue一定在其左子树所以当curValue大于rootValue时说明其不是二叉搜索树。if (curValue rootValue) return false;//当curValue小于其前一个节点时说明curValue不是其前一个节点的右节点我们通过栈找到curValue的父节点并更新rootValuewhile (!stack.isEmpty() curValue stack.peek()) {rootValue stack.pop();}stack.push(curValue);}return true;}
}
