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

Bertha 。 2024-04-17 15:27 19阅读 0赞

1.  二叉搜索树  
    二叉搜索树又名二叉查找树、二叉排序树，见名知意，它是一颗有序的树。分为两种状态：
    
    1.  该树是一棵空树
    2.  该树符合以下定义：  
        如果有左子树，则所有的左子树结点的值都比根结点小；如果有右子树，则所有右子树结点的值都比根结点大。所有的左右子树都符合上述规律。
2.  思考该题
    
    1.  题目  
        输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
    2.  思路  
        由上述可以知道，对于一颗二叉搜索树而言，利用后序遍历会让整个数组分为两部分：前面部分为左子树，其所有值都比根结点（即是数组最后一个数值）小；后半部分为右子树，其所有值都比根结点大。并且，该特性在子树中也适用。  
        所以，我们可以利用该特性去解决该问题。  
        图示上述特性：  
        ![字丑，莫怪][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Mjk1NTEx_size_16_color_FFFFFF_t_70]
    3.  代码结果：  
        ![在这里插入图片描述][20190827235540302.png]
    4.  代码：
    
        public class Solution { 
            public boolean VerifySquenceOfBST(int [] sequence) { 
                if(sequence.length == 0) return false;
                return VerifySequenceOfBST(sequence, 0, sequence.length - 1);
            }
            public boolean VerifySequenceOfBST(int[] sequence, int begin, int end){ 
                if(end - begin == 0) return true;
                for(int i =0;i<end ;i++){ 
                    if(sequence[i] < sequence[end]){ 
                        continue;
                    }
                    for(int j=i+1;j<end;j++){ 
                        if(sequence[j] < sequence[end]){ 
                            return false;
                        }
                    }
                    return VerifySequenceOfBST(sequence, begin, i) && VerifySequenceOfBST(sequence, i+1, end-1);
                    //因为上面已经把根结点比较过了，所以舍弃了根结点（即是最后一个点）
                }
                return true;
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Mjk1NTEx_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/e731f59d20af400890d91b81d2604ae4.png
[20190827235540302.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/37607b89941d4eb7b45f0488d6cd07a3.png