Leecode 669. 修剪二叉搜索樹

題目描述

給你二叉搜索樹的根節點 root ，同時給定最小邊界low 和最大邊界 high。通過修剪二叉搜索樹，使得所有節點的值在[low, high]中。修剪樹 不應該 改變保留在樹中的元素的相對結構 (即，如果沒有被移除，原有的父代子代關系都應當保留)。 可以證明，存在 唯一的答案 。

所以結果應當返回修剪好的二叉搜索樹的新的根節點。注意，根節點可能會根據給定的邊界發生改變。

• 示例 1：

輸入：root = [1,0,2], low = 1, high = 2
輸出：[1,null,2]

• 示例 2：

輸入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
輸出：[3,2,null,1]

遞歸法解題思路與代碼

本題要求修剪二叉搜索樹中大于和小于目標區間的節點，最基本的是需要知道二叉搜索樹的性質，其向下投影（中序遍歷）即為有序序列。其次的關鍵在于要對每個節點的可能情形都進行分類討論，此時需要注意不能漏掉某一情形，同時要清晰對于每種情況都要如何操作。首先我們先討論如何來進行分情況討論。

每個節點的值可能取到的大小0 <= low <= high <= 10^4，同時我們需要保留其中取值在[low, high]閉區間內的值，那么就相當于把數軸劃分為三段，分別為：

• [0，low)，在代碼中可以具體表示為Node->val < low；
• [low, high]，即Node->val >= low && Node->val <= high；
• (high, 10^4]，即Node->val > high。

根據上面的分類情況，就能考慮到每一個節點的所有情況，接下來我們再說明對于其中每一種情況需要如何處理：

• 當Node->val < low時，當前節點及其左子樹都不滿足條件，但是右子樹是否滿足還未知。因此可以考慮使用右子節點來替代當前節點，繼續遞歸處理當前節點
• 當Node->val >= low && Node->val <= high時，當前節點滿足條件，此時遞歸處理左右子樹
• 當Node->val > high時，類似第一種情況，右子樹和當前節點都不滿足，用左子節點來替代當前節點。并再將當前節點傳入遞歸

根據上面算法思想，即可實現如下代碼：

class Solution {
public:
    void cutHelper(TreeNode*& curNode, int low, int high){
        if(!curNode) return; // 如果當前節點已經為空，則直接返回
        if(curNode->val < low) { // 如果當前節點已經小于下界，則用其右子節點來替代當前節點
            if(curNode->val < low)curNode = curNode->right; // 用右子節點來替代當前節點
            if(curNode)cutHelper(curNode, low, high); // 繼續將當前節點傳入遞歸修剪（因當前節點已經被替換，所以繼續傳當前節點）
        }
        else if(curNode->val >= low && curNode->val <= high){ // 如果當前節點滿足條件，則需要分別對左右子樹進行修剪
             cutHelper(curNode->left, low, high); // 遞歸修剪左子樹
             cutHelper(curNode->right, low, high); // 遞歸修剪右子樹
        }
        else if(curNode->val > high){ // 如果當前節點的值大于上界，則將
            if(curNode->val > high) curNode = curNode->left; 
            if(curNode)cutHelper(curNode, low, high);
        }
    }

    TreeNode* trimBST(TreeNode* root, int low, int high) {
        cutHelper(root, low, high);
        return root;
    }
};

上面代碼的最壞時間復雜度為\(O(n)\)，即每個節點都需要進行一次判斷，判斷其是否落在區間內。但實際上每次判斷后根據二叉搜索樹的性質，可以知道當前節點左右子樹是否有可能滿足，從而省略一部分判斷用時從而減少時間復雜度。

Leecode 108. 將有序數組轉換為二叉搜索樹

題目描述

給你一個整數數組 nums ，其中元素已經按 升序 排列，請你將其轉換為一棵 平衡 二叉搜索樹。

• 示例 1：

輸入：nums = [-10,-3,0,5,9]
輸出：[0,-3,9,-10,null,5]
解釋：[0,-10,5,null,-3,null,9] 也將被視為正確答案：

• 示例 2：

輸入：nums = [1,3]
輸出：[3,1]
解釋：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索樹。

解題思路與代碼展示

本題是建立二叉樹的題目，此前已經做過幾道類似的題目。關鍵在于劃分數組，以用于建立當前節點的值作為分割點，將數組分為兩半，并后續分別用于遞歸構造左右子樹。本題特別的點在于是需要建立平衡的二叉搜索樹，為了平衡性，我們可以考慮每次使用當前數組的中點作為當前節點的值并對數組進行分割，這樣就可以保證左右子樹中的節點個數只相差1，從而確保了平衡性。

class Solution {
public:
    void buildHelper(TreeNode*& curRoot, vector<int> curVec){
        if(curVec.empty()) return; // 如果當前向量已經為空，則直接返回
        int cutPoint = curVec.size()/2 ; // 使用有序數組的中點作為分割點
        curRoot = new TreeNode(curVec[cutPoint]); // 使用中點值來建立當前節點

        vector<int> leftVec(curVec.begin(), curVec.begin()+cutPoint); // 建立左子數組
        buildHelper(curRoot->left, leftVec);  // 遞歸建立左子樹

        vector<int> rightVec(curVec.begin()+cutPoint+1,curVec.end()); // 建立右子數組
        buildHelper(curRoot->right, rightVec); // 遞歸建立右子樹

        return;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* root = nullptr; // 討論空節點的情況
        buildHelper(root, nums); // 調用遞歸函數進行建樹
        return root;
    }
};

Leecode 538. 把二叉搜索樹轉換為累加樹

題目描述

給出二叉 搜索 樹的根節點，該樹的節點值各不相同，請你將其轉換為累加樹（Greater Sum Tree），使每個節點 node 的新值等于原樹中大于或等于 node.val 的值之和。

提醒一下，二叉搜索樹滿足下列約束條件：

節點的左子樹僅包含鍵 小于 節點鍵的節點。
節點的右子樹僅包含鍵 大于 節點鍵的節點。
左右子樹也必須是二叉搜索樹。

• 示例 1：

輸入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
輸出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

• 示例 2：

輸入：root = [0,null,1]
輸出：[1,null,1]

• 示例 3：

輸入：root = [1,0,2]
輸出：[3,3,2]

• 示例 4：

輸入：root = [3,2,4,1]
輸出：[7,9,4,10]

遞歸法 解題思路與代碼

本題使用遞歸來進行深度優先算法。因為要將每個節點轉換為本身與右邊所有節點的和，所以可以知道一開始必須走到最左邊的那個節點并記錄求和值。只要能夠想通深度優先就是中序遍歷，那么本題就沒有什么難度了。直接在中序遍歷遞歸的基礎上，將其更改為記錄求和并更新當前節點的操作即可。故有下面代碼：

class Solution {
public:
    void convertHelper(TreeNode* curNode, int& sum){ // 使用中序遍歷來進行遞歸
        if(!curNode) return; // 如果當前節點為空則返回
        convertHelper(curNode->right, sum); // 向右遞歸

        sum += curNode->val;  // 將當前節點值加到sum上
        curNode->val = sum;  // 在令當前節點值等于sum

        convertHelper(curNode->left, sum); // 向左遞歸
    }

    TreeNode* convertBST(TreeNode* root) {
        int sum = 0;
        convertHelper(root, sum);
        return root;
    }
};

時間復雜度為\(O(n)\)，即每個節點遍歷一次。

今日總結

實際上是昨日總結...因為本來該4.15發的打卡到了4.16才發，原因是昨天去看了DragonForce北京演出。

發現二叉樹部分的題目暫時算是刷完了，總的來說感覺大部分題目用遞歸來解決都并不算難，關鍵在于說要去往前、中、后序遍歷的方向去套。以及遞歸中需要分情況討論的地方要把所有可能性都考慮到，那么就基本都能做出來。

同時還有一個非常重要的點在于，在層序遍歷中使用隊列來解決問題的范式模板，注意當需要分層解決問題的時候，需要固定每一次循環開始時的隊列長度，用于表示當前層的節點個數。

二叉樹最難的地方感覺就在于，使用迭代來求解的時候，對于前序遍歷和中序遍歷的迭代法需要充分掌握。還有就是當遇到需要自下而上的算法的時候，需要使用回溯的方式。對于回溯算法，如果使用遞歸來實現，使用值傳遞可以免去一次pop出棧操作，但是值傳遞可能會導致每一次遞歸都復制一個棧，當數據量較大時會占用很大的空間。如果使用引用的方式進行回溯，則每次遞歸之后要手動使用pop進行回溯。

大致上總結了一下最近學到的東西，以及記錄當前力扣進度：

目前力扣已經79題了，100題盡在眼前，繼續加油