天天看點
傳回

二叉搜尋樹（LeetCode相關題解（遞歸求解））前言一、什麼是二叉搜尋樹二、二叉搜尋樹的操作

前言

  • LeetCode 700：二叉搜尋樹中的搜尋
  • LeetCode 701：二叉搜尋樹的插入操作
  • LeetCode 450：删除二叉搜尋樹中的節點
  • LeetCode 108：将有序數組轉換成二叉搜尋樹

一、什麼是二叉搜尋樹

1、空樹是二叉搜尋樹

2、若不為空則應具有以下3條性質：

  • 若它的左子樹不為空，則左子樹上所有節點的值均小于它的根節點的值；
  • 若它的右子樹不為空，則右子樹上所有節點的值均小于它的根節點的值；
  • 它的左右子樹也均為二叉搜尋樹.

前提：二叉搜尋樹首先是一個二叉樹。

二、二叉搜尋樹的操作

1.查找（遞歸查找是否存在key值）

LeetCode 700題：二叉搜尋樹中的搜尋

給定二叉搜尋樹（BST）的根節點和一個值。 你需要在BST中找到節點值等于給定值的節點。 傳回以該節點為根的子樹。 如果節點不存在，則傳回 NULL。

例如，

給定二叉搜尋樹:

4
   / \
  2   7
 / \
1   3

和值: 2

你應該傳回如下子樹:

2     
 / \   
1   3

在上述示例中，如果要找的值是 5，但因為沒有節點值為 5，我們應該傳回 NULL。

（1）解題思路：

本題首先根據給定的根節點查找到目标節點key：二叉搜尋樹中的查找不需要周遊所有節點，二叉搜尋樹是一棵排序樹，其中序周遊的結果是一個從小到大排序的數組，故在二叉搜尋樹中查找某個key值隻需要搜尋一條路徑。

然後傳回查找到的節點，完畢。

（2）代碼如下： 

class Solution {
public:
    TreeNode* traversal(TreeNode* cur,int val){
        if(cur==NULL) return NULL;//終止程式的條件
        if(cur->val>val){//若目前節點的值>val,則說明val存在于目前節點的左子樹中，故需要向左查找
            return searchBST(cur->left,val);
        }else if(cur->val<val){//若目前節點的值<val,則說明val存在于目前節點的右子樹中，故需要向右查找
            return searchBST(cur->right,val);
        }else{//若目前節點的值==val，則傳回目前節點
            return cur;
        }
    }
    TreeNode* searchBST(TreeNode* root, int val) {
        return traversal(root,val);
    }
};

舉例說明：

給定二叉搜尋樹:

4
   / \
  2   7
 / \
1   3

和值: 2

若需要找到其樹中值為2的節點，隻需要從根節點向左查找到值為2節點即可，不需要向右查找，因為根節點右子樹上節點的值均大于根節點的值，故對于二叉搜尋樹的查找操作隻需要搜尋一條路徑，不需要周遊整棵樹。

（3）遞歸步驟（以上述例子為例）:

  • 當 cur==root 時為0層，遞歸函數 traversal 執行到 return searchBST(cur->left,val); 進入1層遞歸；
  • 當 cur==root->left 時為1層，遞歸函數 traversal 執行到 return cur; 得到了1層遞歸的傳回值cur（cur為root->left），此時遞歸函數進入0層；
  • 此時 cur==root 為0層，隻有0層時的return才會結束遞歸函數。

（4）注意：

具有傳回值的遞歸函數要牢記遞歸函數定義以及遞歸函數傳回值是什麼，在本題中遞歸函數的定義是：

  • 找到值等于val的節點（是以 return searchBST(cur->left,val); 表示程式最終傳回了值為val的節點，實際上函數到達0層的這條語句就結束了）

遞歸函數的傳回值是什麼：

  • 若能找到節點，則傳回值為值等于val的節點；
  • 若不能找到節點，則傳回值為NULL節點。

2.插入（原樹中不存在key，插入key）

LeetCode 701：二叉搜尋樹的插入操作

給定二叉搜尋樹（BST）的根節點和要插入樹中的值，将值插入二叉搜尋樹。 傳回插入後二叉搜尋樹的根節點。 輸入資料 保證 ，新值和原始二叉搜尋樹中的任意節點值都不同。

注意，可能存在多種有效的插入方式，隻要樹在插入後仍保持為二叉搜尋樹即可。 你可以傳回 任意有效的結果 。

示例 1：

二叉搜尋樹（LeetCode相關題解（遞歸求解））前言一、什麼是二叉搜尋樹二、二叉搜尋樹的操作

輸入：root = [4,2,7,1,3], val = 5

輸出：[4,2,7,1,3,5]

示例 2：

輸入：root = [40,20,60,10,30,50,70], val = 25

輸出：[40,20,60,10,30,50,70,null,null,25]

示例 3：

輸入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5

輸出：[4,2,7,1,3,5]

（1）解題思路：

本題首先需要找到需要插入節點的位置，根據二叉搜尋樹的有序性很容易找到，關鍵是怎麼處理需要插入的節點（如何将節點插入到指定位置），很顯然本題可用遞歸求解，那麼遞歸函數如何去寫，需要回答以下2個問題。

  1. 遞歸函數如何定義
  2. 遞歸函數的傳回值是什麼

回答：

1、本題的目的是為了将給定數值val插入到二叉搜尋樹中，故遞歸函數應定義為将值為val的節點插入樹中

2、遞歸函數的傳回值是什麼

  • 若目前節點為NULL，則傳回新節點
  • 若目前節點不為NULL，則傳回含有新節點的樹

（2）代碼如下： 

class Solution {
public:
    TreeNode* traversal(TreeNode* cur,int val){
        //遞歸函數的定義是将值為val的節點插入樹中
        //遞歸函數傳回值的是含有新節點的樹
        if(cur==NULL){//傳回新節點
            TreeNode* newNode=new TreeNode(val);
            return newNode;
        }
        if(cur->val<val){
            cur->right=traversal(cur->right,val);//将含有新節點的子樹插入樹中
        }else if(cur->val>val){
            cur->left=traversal(cur->left,val);
        }
        return cur;//傳回含有新節點的樹
    }
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        return traversal(root,val);
    }
};

（3）遞歸步驟（以示例1為例）：

二叉搜尋樹（LeetCode相關題解（遞歸求解））前言一、什麼是二叉搜尋樹二、二叉搜尋樹的操作
  • 當cur==root時為0層，遞歸函數 traversal 執行到 cur->right=traversal(cur->right,val); 進入1層遞歸；
  • 此時cur==root->right為1層，遞歸函數 traversal 執行到 cur->left=traversal(cur->left,val); 進入2層遞歸；
  • 此時cur==root->right->left為2層，遞歸函數執行到 return newNode; 傳回到1層遞歸；
  • 此時cur==root->right為1層，執行複制操作使得cur->left為newNode，遞歸函數繼續執行到 return cur; 傳回到0層；
  • 此時cur==root為0層，并且cur->right->left為newNode。

3.删除（删除樹中節點，使得删除後仍為二差搜尋樹）

LeetCode 450：删除二叉搜尋樹中的節點

給定一個二叉搜尋樹的根節點 root 和一個值 key，删除二叉搜尋樹中的 key 對應的節點，并保證二叉搜尋樹的性質不變。傳回二叉搜尋樹（有可能被更新）的根節點的引用。

一般來說，删除節點可分為兩個步驟：

  • 首先找到需要删除的節點；
  • 如果找到了，删除它。

說明： 要求算法時間複雜度為 O(h)，h 為樹的高度。

示例:

root = [5,3,6,2,4,null,7]

key = 3

5
   / \
  3   6
 / \   \
2   4   7

給定需要删除的節點值是 3，是以我們首先找到 3 這個節點，然後删除它。

一個正确的答案是 [5,4,6,2,null,null,7]

（1）解題思路：

本題首先需要找到需要删除節點的位置，根據二叉搜尋樹的有序性很容易找到，要注意的是要删除的節點有以下3種情況：

  1. 該節點為葉子節點，隻需要将此節點删除即可；
  2. 該節點隻有左孩子或隻有有孩子，若隻有左孩子，需将左孩子賦給該節點，若隻有右孩子，需将右孩子賦給該節點；
  3. 該節點既有左孩子又有右孩子，設該節點右孩子節點為目前節點，不斷向下找到目前節點的左孩子節點，直到目前節點的左孩子為NULL，再将該節點的左孩子指派給目前節點的左孩子，最後将該節點右孩子指派給該節點。

舉例

在題目給出的示例中為第3種情況，要删除節點為值為3的節點，需找到值為3節點的右孩子節點（值為4的節點）将其設為目前節點，不斷向下找到目前節點的左孩子節點，由于值為4的節點左孩子為NULL，故将值為3的節點的左孩子節點（值為2的節點）指派給值為4的節點的左孩子。

結果如下：

5
   / \
  4   6
 /     \
2       7

遞歸函數的定義和傳回值：

1、遞歸函數應定義為删除值為val的節點

2、遞歸函數的傳回值是傳回删除節點後的樹

（2）代碼如下： 

class Solution {
public:
    TreeNode* traversal(TreeNode* cur,int key){
        //1.删除節點為葉子節點
        //2.删除節點為其他節點，分為
        //(1)僅有左或右子樹的節點
        //(2)左右子樹均有的節點
        if(cur==NULL) return NULL;
        if(cur->val==key){
            if(cur->left==NULL && cur->right==NULL){
                return NULL;//目前節點無左右孩子直接傳回空（将目前節點删除即為空樹）
            }else if(cur->left==NULL && cur->right!=NULL){
                return cur->right;//無左孩子有右孩子傳回右孩子
            }else if(cur->left!=NULL && cur->right==NULL){
                return cur->left;//無右孩子有左孩子傳回左孩子
            }else if(cur->left!=NULL && cur->right!=NULL){
                TreeNode* newNode=cur;//見上述删除節點的第3種情況
                cur=cur->right;
                while(cur->left!=NULL){
                    cur=cur->left;
                }
                cur->left=newNode->left;
                TreeNode* tmp=newNode;
                newNode=newNode->right;
                delete tmp;
                return newNode;
            }
        }
        if(cur->val>key) cur->left=traversal(cur->left,key);//遞歸函數為傳回删除節點之後的樹（有則删，沒有不删）
        if(cur->val<key) cur->right=traversal(cur->right,key);//遞歸函數為傳回删除節點之後的樹（有則删，沒有不删）
        return cur;
    }
    TreeNode* deleteNode(TreeNode* root, int key) {
        return traversal(root,key);
    }
};

（3）遞歸步驟（以本題示例為例）： 

5
   / \
  3   6
 / \   \
2   4   7

删除值為3的節點

  • 當cur==root時為0層，遞歸函數traversal執行到 cur->left=traversal(cur->left,key); 進入1層；
  • 此時cur==root->left時為1層，此時遞歸函數traversal執行 if(cur->left!=NULL && cur->right!=NULL) 中的内容，執行到 return newNode; 傳回删除節點之後的樹，傳回0層；
  • 此時cur==root，并且cur->left為newNode（删除節點之後的子樹）；

4.構造（遞歸插入節點）

LeetCode 108：将有序數組轉換成二叉搜尋樹

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

高度平衡 二叉樹是一棵滿足「每個節點的左右兩個子樹的高度差的絕對值不超過 1 」的二叉樹。

示例 1：

二叉搜尋樹（LeetCode相關題解（遞歸求解））前言一、什麼是二叉搜尋樹二、二叉搜尋樹的操作

輸入：nums = [-10,-3,0,5,9]

輸出：[0,-10,5,null,-3,null,9]

（1）解題思路：

本題旨在根據給定的有序數組構造一棵高度平衡的二叉搜尋樹，是以必然要周遊整棵樹，且每次取中間元素進行構造。是因為要保持高度平衡，就要滿足每個節點左右子樹高度絕對值差小于等于1，那麼左右子樹節點個數絕對值差需小于等于1。本題遞歸的思路采用前序周遊的思路，每次構造一個中間節點，再向左向右周遊。

遞歸函數的定義和傳回值：

1、遞歸函數應定義為前序周遊

2、遞歸函數的傳回值是傳回一棵高度平衡的二叉樹

（2）代碼如下： 

class Solution {
public:
    TreeNode* traversal(vector<int>& nums){
        if(nums.size()==0) return NULL;
        int mid=(nums.size()-1)/2;
        TreeNode* root=new TreeNode(nums[mid]);
        vector<int> leftNums(nums.begin(),nums.begin()+mid);
        vector<int> rightNums(nums.begin()+mid+1,nums.end());
        root->left=traversal(leftNums);
        root->right=traversal(rightNums);
        return root; 
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return traversal(nums);
    }
};

（3）遞歸步驟（以本題示例為例）：

  • 當nums[mid]為0時為0層，root值為0，遞歸函數執行到 root->left=traversal(leftNums); 時進入1層；
  • 此時nums[mid]為-10為1層，root->left值為-10，遞歸函數執行到 root->left=traversal(leftNums); 時進入2層；
  • 由于此時leftNums為空，故傳回1層；
  • 此時nums[mid]為-10為1層，root->left->right值為-10，遞歸函數執行到 root->right=traversal(rightNums); 時進入2層；
  • 由于此時leftNums以及rightNums均為空，傳回1層；
  • 此時nums[mid]為5時為1層，root->right值為5，遞歸函數執行到 root->right=traversal(rightNums); 時進入2層；
  • 由于此時leftNums為空，故傳回1層；
  • 此時nums[mid]為9為1層，root->right->right值為9，遞歸函數執行到 root->right=traversal(rightNums); 時進入2層；
  • 由于此時leftNums以及rightNums均為空，傳回1層；
  • 此時nums[mid]為5時為1層，遞歸函數執行到 return root; 傳回0層；
  • 當nums[mid]為0時為0層，遞歸函數執行到 return root; 跳出循環。

參考文獻：

[1]: https://leetcode-cn.com/problemset/all/

[2]: https://mp.weixin.qq.com/s/weyitJcVHBgFtSc19cbPdw

Leetcode刷題筆記 leetcode
上一篇: 小米3c虛拟伺服器,小米路由器3和3C哪個好？小米路由器3和3C差別
下一篇: 在Linux虛拟機上安裝QT一 安裝虛拟機二 在虛拟機上安裝Linux三 在Linux上安裝QT

繼續閱讀