转载

二叉搜索树的后序遍历序列

二叉搜索树的后序遍历序列

  • 知识点

    二叉搜索树的定义:

    • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值
    •  若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值
    • 它的左、右子树也分别为二叉搜索树

    例子:

    如图所示二叉树:

    二叉搜索树

  • 题目

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

  • 思想

    抓住二叉搜索树的性质,根节点比左节点大,比右节点小,再结合后序遍历的性质,利用递归实现

  • 代码

    public class Solution {
      public boolean VerifySquenceOfBST(int [] sequence) {
          if(sequence == null) return false;
          if(sequence.length <= 0) return false;
          if(sequence.length == 1) return true;
    
          int root = sequence[sequence.length -1];
          int index = sequence.length -1;
    
          for(int i = 0; i < sequence.length; i++) {
              if(sequence[i] > root) {
                  index = i;
                  break;
              }
          }
    
          /*左子树*/
          if(index != 0){
              int[] left = new int[index];
    
               for(int i = 0; i < index; i++) {
                  if(sequence[i] >= root) return false;
               }
    
              for(int i = 0; i < index; i++) {
                  left[i] = sequence[i]; 
              }
              if(!VerifySquenceOfBST(left)) return false;
          }
    
          /*右子树*/
          if(index != (sequence.length - 1)) {
             for(int i = index + 1; i < sequence.length - 1; i++) {
                 if(sequence[i] <= root) return false;
             }
    
             int j = 0;
             int[] right = new int[sequence.length - index -1];
             for(int i = index; i < sequence.length - 1; i++) {
                 right[j++] = sequence[i];
             }
             if(!VerifySquenceOfBST(right)) return false;
          }
          return true;
      }
    }
正文到此结束
本文目录