我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷題原始碼[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 面試題33. 二叉搜索樹的后序遍歷序列
題目
輸入一個整數陣列，判斷該陣列是不是某二叉搜索樹的后序遍歷結果，如果是則回傳 true，否則回傳 false，假設輸入的陣列的任意兩個數字都互不相同，
參考以下這顆二叉搜索樹：
5
/ \
2 6
/ \
1 3
示例 1：
輸入: [1,6,3,2,5]
輸出: false
示例 2：
輸入: [1,3,2,6,5]
輸出: true
提示：
- 陣列長度 <= 1000
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解題思路
思路1-分治遞回
后序遍歷：left->right->root；
因此，陣列的最后一個元素是根節點，而陣列的前一部分是左子樹，后一部分是右子樹；
那么，根據搜索二叉樹的特性，左子樹都小于根節點，右子樹都大于根節點，依此校驗即可；
以上述左右子樹的分割點可將陣列分為兩部分，然后各自遞回校驗；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(n^{2}\right)}} $
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $ 遞回堆疊的深度
思路2-使用輔助單調堆疊
后序遍歷：left->right->root；
考慮對陣列倒序遍歷，那么節點的情況就變為：root->right->left；
root為根，然后是右子樹，左子樹，那么以root作為堆疊底，逆序先處理的是右子樹節點，均大于root值，按序入堆疊；
當遇到小于堆疊頂元素的值時，表明右子樹已經全入堆疊了，那么此時可以清空堆疊，開始對左子樹的遞回處理，且根元素更新為左子樹的根；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
演算法原始碼示例
package leetcode;
import java.util.Stack;
/**
* @author ZhouJie
* @date 2020年5月22日 下午6:31:34
* @Description: 面試題33. 二叉搜索樹的后序遍歷序列
*
*/
public class LeetCode_Offer_33 {
}
class Solution_Offer_33 {
/**
* @author: ZhouJie
* @date: 2020年5月22日 下午6:32:04
* @param: @param postorder
* @param: @return
* @return: boolean
* @Description: 1-后序遍歷：left->right->root；
* 陣列最后一個元素是根元素，陣列靠前一段是左子樹，靠后一段是右子樹；
* 二叉搜索樹的特性，根元素大于左子樹小于右子樹，以此校驗；
* 初始的左右子樹分割后的部分也符合校驗模式，故可遞回校驗處理；
*
*/
public boolean verifyPostorder_1(int[] postorder) {
return verifyHelper(postorder, 0, postorder.length - 1);
}
private boolean verifyHelper(int[] postorder, int start, int end) {
if (start >= end) {
return true;
} else {
int i = start;
// 左子樹都小于根節點
while (i < end && postorder[i] < postorder[end]) {
i++;
}
int j = i;
// 右子樹都大于根節點，一旦小于則直接回傳
while (j < end) {
if (postorder[j] < postorder[end]) {
return false;
}
j++;
}
// 以i分割左右子樹遞回校驗
return verifyHelper(postorder, start, i - 1) && verifyHelper(postorder, i, end - 1);
}
}
/**
* @author: ZhouJie
* @date: 2020年5月22日 下午7:18:15
* @param: @param postorder
* @param: @return
* @return: boolean
* @Description: 2-單調輔助堆疊校驗；
* 后序遍歷：left->right->root；
* 若對陣列逆序遍歷，則對應節點順序為：root->right->left；
* root作為堆疊最底的元素，先校驗右子樹都大于root的部分，當遇到小于堆疊頂的元素時，表明到了左子樹，此時清空堆疊開始處理左子樹；
*
*/
public boolean verifyPostorder_(int[] postorder) {
Stack<Integer> stack = new Stack<Integer>();
// 初始化根節點
int root = Integer.MAX_VALUE;
for (int i = postorder.length - 1; i > -1; i--) {
// 若左子樹中有大于根節點的值，直接回傳false
if (postorder[i] > root) {
return false;
}
// 若當前值小于堆疊頂的值，說明右子樹已經遍歷完畢，堆疊中都是右子樹，清空堆疊，但記錄根元素，然后左子樹入堆疊
while (!stack.isEmpty() && postorder[i] < stack.peek()) {
root = stack.pop();
}
// 若堆疊為空是右子樹入堆疊，否則為左子樹入堆疊
stack.push(postorder[i]);
}
return true;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/185234.html
標籤：Java