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

ゝ一纸荒年。 2022-11-27 06:54 142阅读 0赞

[NowCoder][]

## 题目描述 ##

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

例如，下图是后序遍历序列 1,3,2 所对应的二叉搜索树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2OTY4MA_size_16_color_FFFFFF_t_70_pic_center]

public class Solution { 
        public boolean VerifySquenceOfBST(int [] sequence) { 
            if(sequence == null || sequence.length == 0)
                return false;
            return verify(sequence, 0, sequence.length-1);
        }
        private boolean verify(int[] sequence, int first, int last) { 
            // 终止
            if(last-first <= 1)
                return true;
            
            int curIndex = first;
            int root = sequence[last];
            
            // 树左
            while(curIndex<last && sequence[curIndex]<=root) 
                curIndex++;
            
            // 树右
            for(int i=curIndex; i<last; i++) { 
                if(sequence[i]<root)
                    return false;
            }
            
            // 递归
            return verify(sequence, first, curIndex-1) && verify(sequence, curIndex, last-1);
        }
    }

public class Solution { 
        public boolean VerifySquenceOfBST(int [] sequence) { 
            if(sequence == null || sequence.length == 0) return false;
            return dfs(sequence, 0, sequence.length-1);
        }
        
        private boolean dfs(int [] arr, int l, int r) { 
            // 临界判断
            if(l >= r) return true;
            
            int p = l;
            int root = arr[r];
            
            // 左
            while(arr[p] < root) p++;
            int m = p;
            
            // 右
            while(arr[p] > root) p++;
            
            return (p == r) && dfs(arr, l, m-1) && dfs(arr, m, r-1);
        }
    }

[NowCoder]: https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?tpId=13&tqId=11176&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=bennyrhys@163.com
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2OTY4MA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/8b8c430ee56b418bbace6ce46978afcf.png