[[422022]]

如果不對遞歸有深刻的理解，本題有點(diǎn)難。單純移除一個(gè)節(jié)點(diǎn)那還不夠，要修剪!

修剪二叉搜索樹

力扣鏈接：https://leetcode-cn.com/problems/trim-a-binary-search-tree/

給定一個(gè)二叉搜索樹，同時(shí)給定最小邊界L 和最大邊界 R。通過修剪二叉搜索樹，使得所有節(jié)點(diǎn)的值在[L, R]中 (R>=L) 。你可能需要改變樹的根節(jié)點(diǎn)，所以結(jié)果應(yīng)當(dāng)返回修剪好的二叉搜索樹的新的根節(jié)點(diǎn)。

思路

相信看到這道題目大家都感覺是一道簡單題(事實(shí)上leetcode上也標(biāo)明是簡單)。

但還真的不簡單!

遞歸法

直接想法就是：遞歸處理，然后遇到 root->val < low || root->val > high 的時(shí)候直接return NULL，一波修改，趕緊利落。

不難寫出如下代碼：

class Solution { 
public: 
    TreeNode* trimBST(TreeNode* root, int low, int high) { 
        if (root == nullptr || root->val < low || root->val > high) return nullptr; 
        root->left = trimBST(root->left, low, high); 
        root->right = trimBST(root->right, low, high); 
        return root; 
    } 
}; 

然而[1, 3]區(qū)間在二叉搜索樹的中可不是單純的節(jié)點(diǎn)3和左孩子節(jié)點(diǎn)0就決定的，還要考慮節(jié)點(diǎn)0的右子樹。

我們在重新關(guān)注一下第二個(gè)示例，如圖：

669.修剪二叉搜索樹

所以以上的代碼是不可行的!

從圖中可以看出需要重構(gòu)二叉樹，想想是不是本題就有點(diǎn)復(fù)雜了。

其實(shí)不用重構(gòu)那么復(fù)雜。

在上圖中我們發(fā)現(xiàn)節(jié)點(diǎn)0并不符合區(qū)間要求，那么將節(jié)點(diǎn)0的右孩子 節(jié)點(diǎn)2 直接賦給 節(jié)點(diǎn)3的左孩子就可以了(就是把節(jié)點(diǎn)0從二叉樹中移除)，如圖：

669.修剪二叉搜索樹1

理解了最關(guān)鍵部分了我們在遞歸三部曲：

• 確定遞歸函數(shù)的參數(shù)以及返回值

這里我們?yōu)槭裁葱枰祷刂的?

因?yàn)槭且闅v整棵樹，做修改，其實(shí)不需要返回值也可以，我們也可以完成修剪(其實(shí)就是從二叉樹中移除節(jié)點(diǎn))的操作。

但是有返回值，更方便，可以通過遞歸函數(shù)的返回值來移除節(jié)點(diǎn)。

這樣的做法在二叉樹：搜索樹中的插入操作和二叉樹：搜索樹中的刪除操作中大家已經(jīng)了解過了。

代碼如下：

TreeNode* trimBST(TreeNode* root, int low, int high) 

• 確定終止條件

修剪的操作并不是在終止條件上進(jìn)行的，所以就是遇到空節(jié)點(diǎn)返回就可以了。

if (root == nullptr ) return nullptr; 

• 確定單層遞歸的邏輯

如果root(當(dāng)前節(jié)點(diǎn))的元素小于low的數(shù)值，那么應(yīng)該遞歸右子樹，并返回右子樹符合條件的頭結(jié)點(diǎn)。

代碼如下：

if (root->val < low) { 
    TreeNode* right = trimBST(root->right, low, high); // 尋找符合區(qū)間[low, high]的節(jié)點(diǎn) 
    return right; 
} 

如果root(當(dāng)前節(jié)點(diǎn))的元素大于high的，那么應(yīng)該遞歸左子樹，并返回左子樹符合條件的頭結(jié)點(diǎn)。

代碼如下：

if (root->val > high) { 
    TreeNode* left = trimBST(root->left, low, high); // 尋找符合區(qū)間[low, high]的節(jié)點(diǎn) 
    return left; 
} 

接下來要將下一層處理完左子樹的結(jié)果賦給root->left，處理完右子樹的結(jié)果賦給root->right。

最后返回root節(jié)點(diǎn)，代碼如下：

root->left = trimBST(root->left, low, high); // root->left接入符合條件的左孩子 
root->right = trimBST(root->right, low, high); // root->right接入符合條件的右孩子 
return root; 

此時(shí)大家是不是還沒發(fā)現(xiàn)這多余的節(jié)點(diǎn)究竟是如何從二叉樹中移除的呢?

在回顧一下上面的代碼，針對下圖中二叉樹的情況：

669.修剪二叉搜索樹1

如下代碼相當(dāng)于把節(jié)點(diǎn)0的右孩子(節(jié)點(diǎn)2)返回給上一層，

if (root->val < low) { 
    TreeNode* right = trimBST(root->right, low, high); // 尋找符合區(qū)間[low, high]的節(jié)點(diǎn) 
    return right; 
} 

然后如下代碼相當(dāng)于用節(jié)點(diǎn)3的左孩子 把下一層返回的 節(jié)點(diǎn)0的右孩子(節(jié)點(diǎn)2) 接住。

root->left = trimBST(root->left, low, high); 

此時(shí)節(jié)點(diǎn)3的右孩子就變成了節(jié)點(diǎn)2，將節(jié)點(diǎn)0從二叉樹中移除了。

最后整體代碼如下：

class Solution { 
public: 
    TreeNode* trimBST(TreeNode* root, int low, int high) { 
        if (root == nullptr ) return nullptr; 
        if (root->val < low) { 
            TreeNode* right = trimBST(root->right, low, high); // 尋找符合區(qū)間[low, high]的節(jié)點(diǎn) 
            return right; 
        } 
        if (root->val > high) { 
            TreeNode* left = trimBST(root->left, low, high); // 尋找符合區(qū)間[low, high]的節(jié)點(diǎn) 
            return left; 
        } 
        root->left = trimBST(root->left, low, high); // root->left接入符合條件的左孩子 
        root->right = trimBST(root->right, low, high); // root->right接入符合條件的右孩子 
        return root; 
    } 
}; 

精簡之后代碼如下：

class Solution { 
public: 
    TreeNode* trimBST(TreeNode* root, int low, int high) { 
        if (root == nullptr) return nullptr; 
        if (root->val < low) return trimBST(root->right, low, high); 
        if (root->val > high) return trimBST(root->left, low, high); 
        root->left = trimBST(root->left, low, high); 
        root->right = trimBST(root->right, low, high); 
        return root; 
    } 
}; 

只看代碼，其實(shí)不太好理解節(jié)點(diǎn)是符合移除的，這一塊大家可以自己在模擬模擬!

迭代法

因?yàn)槎嫠阉鳂涞挠行蛐裕恍枰褂脳ＤM遞歸的過程。

在剪枝的時(shí)候，可以分為三步：

• 將root移動到[L, R] 范圍內(nèi)，注意是左閉右閉區(qū)間
• 剪枝左子樹
• 剪枝右子樹

代碼如下：

class Solution { 
public: 
    TreeNode* trimBST(TreeNode* root, int L, int R) { 
        if (!root) return nullptr; 
 
        // 處理頭結(jié)點(diǎn)，讓root移動到[L, R] 范圍內(nèi)，注意是左閉右閉 
        while (root != nullptr && (root->val < L || root->val > R)) { 
            if (root->val < L) root = root->right; // 小于L往右走 
            else root = root->left; // 大于R往左走 
        } 
        TreeNode *cur = root; 
        // 此時(shí)root已經(jīng)在[L, R] 范圍內(nèi)，處理左孩子元素小于L的情況 
        while (cur != nullptr) { 
            while (cur->left && cur->left->val < L) { 
                cur->left = cur->left->right; 
            } 
            cur = cur->left; 
        } 
        cur = root; 
 
        // 此時(shí)root已經(jīng)在[L, R] 范圍內(nèi)，處理右孩子大于R的情況 
        while (cur != nullptr) { 
            while (cur->right && cur->right->val > R) { 
                cur->right = cur->right->left; 
            } 
            cur = cur->right; 
        } 
        return root; 
    } 
}; 

總結(jié)

修剪二叉搜索樹其實(shí)并不難，但在遞歸法中大家可看出我費(fèi)了很大的功夫來講解如何刪除節(jié)點(diǎn)的，這個(gè)思路其實(shí)是比較繞的。

最終的代碼倒是很簡潔。

如果不對遞歸有深刻的理解，這道題目還是有難度的!

本題我依然給出遞歸法和迭代法，初學(xué)者掌握遞歸就可以了，如果想進(jìn)一步學(xué)習(xí)，就把迭代法也寫一寫。

其他語言版本

Java

class Solution { 
    public TreeNode trimBST(TreeNode root, int low, int high) { 
        if (root == null) { 
            return null; 
        } 
        if (root.val < low) { 
            return trimBST(root.right, low, high); 
        } 
        if (root.val > high) { 
            return trimBST(root.left, low, high); 
        } 
        // root在[low,high]范圍內(nèi) 
        root.left = trimBST(root.left, low, high); 
        root.right = trimBST(root.right, low, high); 
        return root; 
    } 
} 

Python

class Solution: 
    def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode: 
        if not root: return root 
        if root.val < low: 
            return self.trimBST(root.right,low,high)  // 尋找符合區(qū)間[low, high]的節(jié)點(diǎn) 
        if root.val > high: 
            return self.trimBST(root.left,low,high)  // 尋找符合區(qū)間[low, high]的節(jié)點(diǎn) 
        root.left = self.trimBST(root.left,low,high)  // root->left接入符合條件的左孩子 
        root.right = self.trimBST(root.right,low,high)   // root->right接入符合條件的右孩子 
        return root 

本文轉(zhuǎn)載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系代碼隨想錄公眾號。