【二叉树专题】剑指 Offer 33. 二叉搜索树的后序遍历序列

共以下 11 个回答

• Miracle· 普通 2023年9月7日 下午6:55

  class Solution {
  public:
  // 递归
  bool travel(vector &postorder, int start, int end) {
  if (start >= end) return true;
  int index = start;
  // 寻找第一个大于根节点的值,即找到根节点的右孩子
  while (postorder[index] < postorder[end]) index++;
  int midindex = index; // 右子树的索引位置
  while (postorder[index] > postorder[end]) index++;//将索引走到不大于end的位置,
  // 递归左右子树
  bool left = travel(postorder, start, midindex – 1);
  bool right = travel(postorder, midindex, end – 1);
  // 如果index能成功到end的位置,认为这是一个搜索二叉树的后序遍历
  return index end && left && right;
  }

  bool verifyPostorder(vector<int>& postorder) {
      return travel(postorder, 0, postorder.size() - 1);
  }
  

  };

  0 赞同 0 条回复

  登录以回复
• Sheng 永久会员 2023年8月29日 上午12:48

  二叉树的后序遍历是中右左为遍历顺序的倒序，根据这种方法分离出根节点，左子树右子树。根据搜索树的性质，左子树节点小于根节点，右子树大于，判断是否为true

      public boolean verifyPostorder(int[] postorder) {
          if(postorder == null || postorder.length == 0) return true;
          int len = postorder.length;
          int[] preorder = new int[len];
          for(int i=0; i<len; i++) {
              preorder[len-i-1] = postorder[i];
          }
  
          return f(arr, 0, len-1);
      }
  
      public boolean f(int[] preorder, int begin, int end) {
          if(begin >= end) return true;
  
          int left = -1;
          int j = 0;
          if(preorder[begin+1] < preorder[begin]) {
              //开始就是左子树
              left = begin + 1;
              for(j=left; j<=end; j++) {
                  if(preorder[j] > preorder[begin]) {
                      return false;//左子树中不能含有大于根节点begin的节点
                  }
              }
              return f(preorder, left, end);//left以后全是左子树
          }
          else {
              //开始是右子树
              int right = begin + 1;
              left = -1;
              for(j = right; j <= end; j++) {
                  if(preorder[j] < preorder[begin]) {
                      left = j;//左子树根节点
                      break;
                  }
              }
              if(left != -1) {
                  for(; j<=end; j++) {
                      if(preorder[j] > preorder[begin]) {
                          return false;//左子树中不能包含大于根节点begin的节点
                      }
                  }
                  return f(preorder, right, left-1) && f(preorder, left, end);//右子树 && 左子树
              }
              else {
                  return f(preorder, right, end);//right以后全是右子树
              }
          }
      }
  

  0 赞同 0 条回复

  登录以回复
• 小肸 永久会员 2023年8月28日 下午4:04

  class Solution {
      //递归写法，树退化成链表时，时间复杂度O(N^2)，空间复杂度O(N)。
      //可以使用单调栈。后序遍历为左 | 右 | 中。而后序遍历的倒序为中 | 右 | 左，所以中 | 右这是递增的，左是递减的
      public boolean verifyPostorder(int[] postorder) {
          return verifyPostorderCore(postorder, 0, postorder.length - 1);
      }
      boolean verifyPostorderCore(int[] postorder, int left, int right) {
          if (left >= right) {
              return true;
          }
          int rootVal = postorder[right];
          int rightIndex = right;
          while (rightIndex >= left && postorder[rightIndex] >= rootVal) {
              rightIndex --;
          }
          int index = rightIndex;
          while (rightIndex >= left && postorder[rightIndex] < rootVal) {
              rightIndex --;
          }
          if (rightIndex >= left) {
              return false;
          } else {
              return verifyPostorderCore(postorder, left, index) && verifyPostorderCore(postorder, index + 1, right - 1);
          }
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• sincere 普通 2023年8月27日 下午10:05

  • 思路：二叉搜索树的后序遍历中，最后一个是根节点，并且二叉搜索树左子树都小于根，右子树都大于根，所以遍历可以找到左右子树的范围，然后递归遍历左右子树
  • 复杂度：时间复杂度O(n2)，空间复杂度O(n)

  class Solution {
      public boolean verifyPostorder(int[] postorder) {
          return build(postorder, 0, postorder.length - 1);
      }
  
      public boolean build(int[] postorder, int start, int end) {
          if (start >= end) {
              return true;
          }
          int tmp = start;
          while (postorder[tmp] < postorder[end]) {
              tmp++;
          }
          int mid = tmp;
          while (postorder[tmp] > postorder[end]) {
              tmp++;
          }
          return (tmp == end) && build(postorder, start, mid - 1) && build(postorder, mid, end - 1);
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• sc_Yang 普通 2023年8月27日 下午6:10

  单独拎出个函数递归

  class Solution {
  public:
      bool verifyPostorder(vector<int>& postorder) {
          if(postorder.size()==0){
              return true;
          }
          return verify(postorder, 0, postorder.size()-1);
      }
      bool verify(vector<int>& postorder, int fir, int lst){
          if(fir>=lst) return true;
          int flag = lst-1;
          // 从前往后数选出第一个大于partition的元素，并且把flag置到那个位置
          while(flag>=fir && postorder[flag]>postorder[lst]){
              flag--;
          }
          for(int i=flag-1; i>=fir; i--){
              if(postorder[i]>postorder[lst]){
                  return false;
              }
          }
          return verify(postorder,fir, flag) && verify(postorder,flag+1, lst-1);
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• c 普通 2023年8月23日 下午9:58

  递归

  class Solution {
      public boolean verifyPostorder(int[] postorder) {
          return fun(postorder,0,postorder.length-1);
      }
      public boolean fun(int[] postorder,int left,int right){
          if(left==right || left+1==right || right+1==left){
              return true;
          }
          int max = postorder[right];
          int index=-1;
          for(int i = left;i<=right-1;i++){
              if(index!=-1){
                  if(postorder[i]<max){
                      return false;
                  }
              }else{
                  if(postorder[i]>max){
                      index=i;
                  }
              }
          }
          if(index==-1){
              index=right;
          }
          return fun(postorder,left,index-1) && fun(postorder,index,right-1);
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 帝心引力 永久会员 2023年8月23日 下午9:50

  时间o(n), 空间o(n)
  class Solution {
  public:
      bool ans = true;
      bool verifyPostorder(vector<int>& postorder) {
          // 后序遍历：左 右 根
          // 最后一个元素为根
          // 遍历数组，第一个比根大的元素为右子树的最小的结点
          // 从这个结点开始往后遍历，如果有比根节点值小的 则不满足题目
          dfs(postorder, 0, postorder.size()-1);
          return ans;
      }
      void dfs(vector<int>& postorder, int l, int r){
          if(l > r || ans==false) return;
          int root_val = postorder[r];
          int i,k;
          for(i=l; i<r && postorder[i]<root_val; i++);
          for(k=i+1;k<r;k++){
              if(postorder[k] < root_val) ans = false;
          }
          dfs(postorder, l, i-1);
          dfs(postorder, i, r-1);
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• JustRtn 普通 2023年8月21日 下午10:01

  后续遍历序列从第一个大于根节点（序列尾）的开始，后面的都应该大于根节点（右子树）

  class Solution {
  public:
      bool f(vector<int>& postorder, int left, int right) {
          if (left >= right) {
              return true;
          }
          int mid = left;
          while (postorder[mid] < postorder[right]) mid++;
          for (int i = mid; i < right; i++) {
              if (postorder[i] < postorder[right]) {
                  return false;
              }
          }
          return f(postorder, left, mid-1) && f(postorder, mid, right - 1);
      }
  
      bool verifyPostorder(vector<int>& postorder) {
          return f(postorder, 0, postorder.size() -1);
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 行动派小彩笔 普通 2023年8月21日 下午9:56

   //时间复杂度最坏O(n^2)
  // 空间复杂度最坏O(n)
  class Solution {
  public:
      bool verify(vector& postorder,int left,int right)
      {
          if(left>=right) return true;
          int root = postorder[right];
          int pos = right-1;
          while((root& postorder) {
          if(postorder.size()<=1) return true;
          return verify(postorder,0,postorder.size()-1);
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 别扒拉我 普通 2023年8月21日 下午9:27

  1、递归

  class Solution {
      public TreeNode buildTree(int[] preorder, int[] inorder) {
          if(preorder.length == 0 || inorder.length == 0){
              return null;
          }
          TreeNode root = new TreeNode(preorder[0]);
          int len = preorder.length;
          for(int i=0; i<len; i++){
              if(inorder[i] == preorder[0]){
                  root.left = buildTree(Arrays.copyOfRange(preorder, 1, i+1), Arrays.copyOfRange(inorder, 0, i));
                  root.right = buildTree(Arrays.copyOfRange(preorder, i+1, len), Arrays.copyOfRange(inorder, i+1, len));
              }
          }
          return root;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 塔底的仰望 永久会员 2023年8月21日 下午5:26

  时间复杂度O(n); 空间复杂度O(n)

  class Solution {
      public TreeNode buildTree(int[] preorder, int[] inorder) {
          if (preorder == null || inorder == null || preorder.length == 0 
              || inorder.length == 0) {
              return null;
          }
  
          return build(preorder, inorder, 0, preorder.length -1, 0, inorder.length -1);
  
      }
  
      public TreeNode build(int[] preorder, int[] inorder, int pl, int pr, int il, int ir) {
          if (pl > pr || il > ir) {
              return null;
          }
          TreeNode root = new TreeNode(preorder[pl]);
          int tag = -1;
          for(int i = il; i <= ir; i++) {
              if (inorder[i] == root.val) {
                  tag = i;
                  break;
              }
          }
          root.left = build(preorder, inorder, pl + 1, pl + tag - il, il, tag -1);
          root.right = build(preorder, inorder, pl + tag -il + 1, pr, tag + 1, ir);
          return root;
      }
  }
  

  0 赞同 0 条回复

  登录以回复