劍指Offer——二叉搜尋樹的後序周遊序列（JS實作）

題目描述

解題思路

• 本題關鍵點在于：二叉搜尋樹的後序周遊序列的最後一個元素是根節點，左子樹均小于根節點，右子樹均大于根節點
• 使用遞歸是本題的解題方法
• 本題需要額外考慮的情況在于有的序列是沒有右子樹的，如果沒有右子樹，那麼分割左右子樹的位置就是根節點所在的位置，預設右子樹是一個空數組

解題代碼

var verifyPostorder = function(postorder) {
    // !本題的解題關鍵：二叉搜尋樹的後序周遊，最後一個元素是根節點
    // 如果輸入的數組長度小于2，則傳回true
    let len = postorder.length;
    if (len < 2) return true;
    // 區分左右子樹 
    let flag = 0;
    // 找到根節點
    let root = postorder[len-1];
    for (let i = 0; i < postorder.length;i++) {
        if (postorder[i] > postorder[len-1]) {
            flag = i;
            break;
        }
        if (i === len-1) {
            flag = i;
        }
    }
    // 左子樹
    let leftTree = postorder.slice(0,flag);
    // 右子樹
    let rightTree = postorder.slice(flag,len-1);

    // 如果右子樹的每一個節點都大于根節點，則繼續遞歸判斷，反之為false
    if (rightTree.every((value) => value > root)) {
        return verifyPostorder(leftTree) && verifyPostorder(rightTree);
    } else {
        return false;
    }
};
      

總結（本題給我們的啟示思路）

• 啟示一：學會使用遞歸求解
• 啟示二：知道二叉搜尋樹的後序周遊序列的最後一個節點是根節點
• 啟示三：知道沒有右子樹的序列，按照空數組來進行處理