题目链接

题目描述

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

例如，下图是后序遍历序列 1,3,2 所对应的二叉搜索树。

33. 二叉搜索树的后序遍历** - 图1
示例：

输入：
[4,8,6,12,16,14,10]
输出：
true

解题思路

方法一：递归

递归简单易懂容易实现，先来一次遍历以确定出左右子树的分界点，然后再分别对两棵子树进行递归判断。现在让我们来分析一下递归方法的时间复杂度：
以标准的完美二叉搜索树为例，递归的每一层都涉及到对序列的遍历，虽然层数越深节点越少（少了子树的根节点），但是这种减少是微不足道的，即使是到了最底层，依旧有n/2的节点（完美二叉树第i层节点数是其上所有节点数之和+1），因此递归方法在每一层的遍历开销是O(n)，而对于二叉树而言，递归的层数平均是O(logn)，因此，递归方法的最终复杂度是O(nlogn)

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size()==0)
            return false;
        return verify(sequence,0,sequence.size()-1);
    }
    bool verify(vector<int> sequence,int start,int end){
        // 当只剩一个结点或者为空时，当前结点为叶子结点或者为空
        if(end-start<=1)
            return true;
        // 获取根结点
        int rootVal = sequence[end];
        int cutIndex = start;
        // 找到左右子树分界处
        while (cutIndex < end && sequence[cutIndex] <= rootVal)
            cutIndex++;
        // 如果右子树中有小于根结点的结点，则不能建立二叉树
        for (int i = cutIndex; i < end; i++)
            if(sequence[i] <= rootVal)
                return false;
        // 递归判断左右子树
        return verify(sequence, start, cutIndex - 1) && verify(sequence, cutIndex, end - 1);
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        // 记录之前遍历的节点
        TreeNode prev = null;
        while(!stack.isEmpty() || root != null){
            // 遍历左子树
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            // 右子树为空或者右子树已经被遍历 遍历当前根节点
            if(root.right == null || root.right == prev){
                res.add(root.val);
                prev = root;
                root = null;
            }else{// 遍历右子树
                stack.push(root);
                root = root.right;
            }
        }
        return res;
    }
}

时间复杂度 O(N)

空间复杂度 O(N)

方法二：morris算法

左子树遍历后，从右子树向当前根节点遍历，由下向上，因为左子树的遍历完后就是这个顺序遍历剩下的。

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
  public List<Integer> postorderTraversal(TreeNode root) {
      List<Integer> res = new ArrayList<Integer>();
      // 后序遍历需要左右子树都先被遍历
      TreeNode p1 = root, p2 = null;
      while(p1 != null){
          // 遍历左子树
          p2 = p1.left;
          if(p2 != null){
              while(p2.right != null && p2.right != p1){
                  p2 = p2.right;
              }
              // 左子树的最右边的节点连接当前根节点
              if(p2.right == null){
                  p2.right = p1;
                  p1 = p1.left;
              }else{// 如果当前根节点已经和左子树连接，说明左子树已经遍历完毕
                  // 一起遍历右子树和根节点，从下向上， 关键
                  p2.right = null;
                  p2 = p1.left;
                  // 记录从当前根节点一直向右走的节点，顺序应该从下向上
                  int pos = res.size();
                  while(p2 != null){
                      res.add(pos, p2.val);
                      p2 = p2.right;
                  }
                  // 遍历当前根节点的右子树
                  p1 = p1.right;
              }
          }else{// 遍历右子树
              p1 = p1.right;
          }
      }
      // 记录从根节点一直向右走的节点，顺序应该从下向上 关键
      int pos = res.size();
      while(root != null){
          res.add(pos, root.val);
          root = root.right;
      }
      return res;
  }
}

时间复杂度 O(N)
空间复杂度 O(1)