做美食网站的意义,谷歌seo怎么做的,常德做网站专业公司哪家好,网络运维个人工作总结我一开始的想法是#xff1a;后序遍历是左右根#xff0c;那么第一个数小于第二个数#xff0c;第二个数大于第三个数#xff0c;然后从第三个数开始又循环#xff0c;显然错了#xff0c;因为我这种是理想情况#xff0c;是一个满二叉树。正确的解法是:
class Solutio… 我一开始的想法是后序遍历是左右根那么第一个数小于第二个数第二个数大于第三个数然后从第三个数开始又循环显然错了因为我这种是理想情况是一个满二叉树。正确的解法是:
class Solution {public boolean verifyPostorder(int[] postorder) {int n postorder.length;return recur(postorder, 0, n-1);}public 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);}
}
后序遍历是[[左子树][右子树][根节点]]左子树中的所有值都小于根节点右子树中的所有值都大于根节点。根节点就是最后一个数所以我们可以从左往右遍历找到第一个大于根节点的数他就是右子树的第一个节点记他的下标为m再继续往后遍历如果m后面的数都大于根节点右子树都大于根节点那么就利用递归继续判断左子树和右子树否则就return false
