面试题33. 二叉搜索树的后序遍历序列

淩亂°似流年 2023-02-13 00:24 2阅读 0赞

# 题目： #

[面试题33. 二叉搜索树的后序遍历序列][33.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]

# 题解： #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]

# 代码： #

public class 面试题33 { 
    
        public static boolean verifyPostorder(int[] postorder) { 
            if(build(postorder, 0, postorder.length - 1))
            { 
                return true;
            }
            return false;
        }
    
        public static boolean build(int[] postorder, int i, int j)
        { 
            if(i >= j)
            { 
                return true;
            }
            int p = i;
            while(postorder[p] < postorder[j])
            { 
                p++;
            }
            // 用 m 记录第一个大于根节点的下标
            int m = p;
            // 判断右子树中是否有比根节点大的节点
            while(postorder[p] > postorder[j])
            { 
                p++;
            }
            if(p == j && build(postorder, i, m - 1) && build(postorder, m, j - 1))
            { 
                return true;            
            }
            return false;
        }
    
        public static void main(String[] args) { 
            // Integer nums[] = { 5, 2, 6, 1, 3 };
            // TreeNode root = ConstructTree.constructTree(nums);
            // TreeOperation.show(root);
    
            int postorder1[] = {  1, 6, 3, 2, 5 };
            boolean res1 = verifyPostorder(postorder1);
            System.out.println(res1);
    
            int postorder2[] = {  1, 3, 2, 6, 5 };
            boolean res2 = verifyPostorder(postorder2);
            System.out.println(res2);
        }
    }

# 参考： #

1.  [面试题33. 二叉搜索树的后序遍历序列（递归分治 / 单调栈，清晰图解）][33. _ _]

[33.]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200526184757109.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020052618483030.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200526184838340.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200526185014449.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200526185040786.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[33. _ _]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/solution/mian-shi-ti-33-er-cha-sou-suo-shu-de-hou-xu-bian-6/