剑指offer 二叉搜搜树的后序遍历序列

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

1 思路

后序遍历即先遍历左子树，再遍历右子树，根节点最后遍历。另外这颗树是二叉搜索树，左子树都比根节点小，右子树都比根节点大。那么输出的序列就有以下特点：
- 最后一个输出的是根节点。
- 前一部分都比根节点小，是左子树。
- 后一部分都比根节点大，是右子树。
根据这个特点，就有一个解题思路：
- 先拿出最后一个数是根节点root。
- 从前向后遍历，找出第一个比root大的位置mid。（消耗O(n)的时间复杂度）
  - 若此序列是二叉搜索树后序遍历的序列，[mid, length -2]中的元素应该都比root大
  - 若符合，则此轮验证成功，若不符合则验证失败
- 若此轮验证成功，那么[0, mid-1]子序列应该是左子树的后序遍历，[mid, length -2]子序列应该是右子树的后序遍历。对这两个子序列递归验证。
- 若两子序列都验证成功，则本序列验证成功。
- 终止条件：若序列长度<=1，则验证成功。
每一轮验证消耗O(n)的时间，最坏情况（树是一个链表）下需要验n轮，所以时间复杂度为O(n^2)。
在思路1中，为了找到左子树和右子树的分割位置，以及后续的验证过程消耗了O(n)的时间，导致最后的时间复杂度为O(n^2)。根据经验，很多O(n^2)时间复杂度的算法可以优化为O(nlogn)时间复杂度。并且此树是二分查找树，我们可以利用其有序的特点，得到一种思路：
- 首先将序列进行排序，得到序列inorder，inorder就是二叉搜索树中序遍历的结果。（消耗O(nlogn)的时间。）那么可以将问题转化为中序遍历序列inorder与后序遍历序列postorder是否匹配的问题。
- 取postorder最后一个元素根节点root，利用二分查找在inorder中找到其位置mid，若无法找到则匹配失败（第一次查找不会失败，因为inorder就是由postorder排序而来，但是在对子序列进行匹配时则有可能失败。这是因为，在思路1中，我们用的验证办法是，在postorder序列中找到左右子树的分割点之后，左子序列应该都小于root，右子序列应该都大于root。在这里我们不这样验证，若右子序列中有小于root的元素，那么这个元素在inorder中是在左子序列中的，接下来我们将inorder和postorder的右子序列进行匹配，那么在后续的匹配过程中，必然会出现以此元素为根节点在inorder序列中查找不到的情况，则匹配失败）。
- 若找到，则以mid为分割点，将inorder的左子序列与postorder中对应长度的左子序列进行匹配，将inorder的右子序列与postorder中对应长度的右子序列进行匹配。
- 若两子序列都匹配成功，则本序列匹配成功。
- 终止条件：匹配序列的长度<=0（这里不是1，因为即使长度是1，但inorder序列与postorder序列不相等的情况也是失败的），则匹配成功。
每一轮验证消耗O(logn)的时间，最坏情况下，需要验证n轮，算法时间复杂度为O(nlogn)，但是需要多记录一个inorder序列，额外空间复杂度为O(n)。

2 java代码

这里实现了思路2的代码：

import java.util.*;

public class Solution {
    
    public boolean VerifySquenceOfBST(int [] sequence) {
        // 1.初始条件
        if (sequence == null || sequence.length ==0) {
            return false;
        }
        
        // 2.复制数组，并将数组排序，得到中序遍历的结果
        int[] inorder = Arrays.copyOf(sequence, sequence.length);
        Arrays.sort(inorder);
        
        // 3.验证sequence和中序遍历的序列是否匹配
        return fit(sequence, 0, sequence.length - 1, inorder, 0, inorder.length - 1);
    }
    
    public boolean fit(int[] postorder, int postStart, int postEnd, int[] inorder, int inStart, int inEnd) {
        // 验证postorder和inorder是否匹配,验证的方法是：
        // 1. 后序遍历的最后一个值应该是根节点，在中序遍历中找到这个根节点
        //    若未找到，则匹配失败
        // 2. 根节点会将中序遍历序列分为两部分，前一部分是左子树，将之与后序遍历的序列中相同长度的前一部分继续匹配
        //    后一部分是右子树，将之与后序遍历中左子树后紧接着的相同长度的后一部分继续匹配
        //    若直到子序列长度为0仍未失败，则匹配成功
        
        // 若序列长度为0，匹配成功
        if (postEnd - postStart < 0) {
            return true;
        }
        
        // 在中序遍历中查找根节点的位置
        int root = Arrays.binarySearch(inorder, inStart, inEnd + 1, postorder[postEnd]);
        // 若未找到，匹配失败
        if (root < 0) {
            return false;
        }
        
        // 若找到将子树继续匹配
        return fit(postorder, postStart, postStart + root - inStart - 1,
                  inorder, inStart, root - 1)
               && fit(postorder, postStart + root - inStart, postEnd - 1,
                     inorder, root + 1, inEnd);
    }
}

剑指offer 二叉搜搜树的后序遍历序列

1 思路

2 java代码

Comments