av激情亚洲男人的天堂国语,日韩欧美精品一中文字幕,无码av一区二区三区无码,国产又色又爽又刺激的a片,国产又色又爽又刺激的a片

聊聊二叉搜索樹中的插入操作

二叉搜索樹中的插入操作

題目鏈接：https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/

成都創(chuàng)新互聯(lián)于2013年開始，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項目網(wǎng)站設(shè)計制作、成都做網(wǎng)站網(wǎng)站策劃，項目實施與項目整合能力。我們以讓每一個夢想脫穎而出為使命，1280元臨猗做網(wǎng)站,已為上家服務(wù),為臨猗各地企業(yè)和個人服務(wù),聯(lián)系電話:13518219792

給定二叉搜索樹(BST)的根節(jié)點和要插入樹中的值，將值插入二叉搜索樹。返回插入后二叉搜索樹的根節(jié)點。輸入數(shù)據(jù)保證，新值和原始二叉搜索樹中的任意節(jié)點值都不同。

注意，可能存在多種有效的插入方式，只要樹在插入后仍保持為二叉搜索樹即可。你可以返回任意有效的結(jié)果。

提示：

  • 給定的樹上的節(jié)點數(shù)介于 0 和 10^4 之間
  • 每個節(jié)點都有一個唯一整數(shù)值，取值范圍從 0 到 10^8
  • -10^8 <= val <= 10^8
  • 新值和原始二叉搜索樹中的任意節(jié)點值都不同

思路

其實這道題目其實是一道簡單題目，但是題目中的提示：有多種有效的插入方式，還可以重構(gòu)二叉搜索樹，一下子嚇退了不少人，瞬間感覺題目復(fù)雜了很多。

其實可以不考慮題目中提示所說的改變樹的結(jié)構(gòu)的插入方式。

如下演示視頻中可以看出：只要按照二叉搜索樹的規(guī)則去遍歷，遇到空節(jié)點就插入節(jié)點就可以了。

二叉搜索樹中的插入操作

例如插入元素10 ，需要找到末尾節(jié)點插入便可，一樣的道理來插入元素15，插入元素0，插入元素6，需要調(diào)整二叉樹的結(jié)構(gòu)么?并不需要。。

只要遍歷二叉搜索樹，找到空節(jié)點 插入元素就可以了，那么這道題其實就簡單了。

接下來就是遍歷二叉搜索樹的過程了。

遞歸

遞歸三部曲：

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

參數(shù)就是根節(jié)點指針，以及要插入元素，這里遞歸函數(shù)要不要有返回值呢?

可以有，也可以沒有，但遞歸函數(shù)如果沒有返回值的話，實現(xiàn)是比較麻煩的，下面也會給出其具體實現(xiàn)代碼。

有返回值的話，可以利用返回值完成新加入的節(jié)點與其父節(jié)點的賦值操作。(下面會進一步解釋)

遞歸函數(shù)的返回類型為節(jié)點類型TreeNode * 。

代碼如下：

 
 
 
 
    
  
  
  
  
  1. TreeNode* insertIntoBST(TreeNode* root, int val)
    2.
  • 確定終止條件

終止條件就是找到遍歷的節(jié)點為null的時候，就是要插入節(jié)點的位置了，并把插入的節(jié)點返回。

代碼如下：

 
 
 
 
    
  
  
  
  
  1. if (root == NULL) {
    2. 
  
  
  
  
  2.     TreeNode* node = new TreeNode(val);
    3. 
  
  
  
  
  3.     return node;
    4. 
  
  
  
  
  4. }
    5.

這里把添加的節(jié)點返回給上一層，就完成了父子節(jié)點的賦值操作了，詳細再往下看。

  • 確定單層遞歸的邏輯

此時要明確，需要遍歷整棵樹么?

別忘了這是搜索樹，遍歷整顆搜索樹簡直是對搜索樹的侮辱，哈哈。

搜索樹是有方向了，可以根據(jù)插入元素的數(shù)值，決定遞歸方向。

代碼如下：

 
 
 
 
    
  
  
  
  
  1. if (root->val > val) root->left = insertIntoBST(root->left, val);
    2. 
  
  
  
  
  2. if (root->val < val) root->right = insertIntoBST(root->right, val);
    3. 
  
  
  
  
  3. return root;
    4.

到這里，大家應(yīng)該能感受到，如何通過遞歸函數(shù)返回值完成了新加入節(jié)點的父子關(guān)系賦值操作了，下一層將加入節(jié)點返回，本層用root->left或者root->right將其接住。

整體代碼如下：

 
 
 
 
    
  
  
  
  
  1. class Solution {
    2. 
  
  
  
  
  2. public:
    3. 
  
  
  
  
  3.     TreeNode* insertIntoBST(TreeNode* root, int val) {
    4. 
  
  
  
  
  4.         if (root == NULL) {
    5. 
  
  
  
  
  5.             TreeNode* node = new TreeNode(val);
    6. 
  
  
  
  
  6.             return node;
    7. 
  
  
  
  
  7.         }
    8. 
  
  
  
  
  8.         if (root->val > val) root->left = insertIntoBST(root->left, val);
    9. 
  
  
  
  
  9.         if (root->val < val) root->right = insertIntoBST(root->right, val);
    10. 
  
  
  
  
  10.         return root;
    11. 
  
  
  
  
  11.     }
    12. 
  
  
  
  
  12. };
    13.

可以看出代碼并不復(fù)雜。

剛剛說了遞歸函數(shù)不用返回值也可以，找到插入的節(jié)點位置，直接讓其父節(jié)點指向插入節(jié)點，結(jié)束遞歸，也是可以的。

那么遞歸函數(shù)定義如下：

 
 
 
 
    
  
  
  
  
  1. TreeNode* parent; // 記錄遍歷節(jié)點的父節(jié)點
    2. 
  
  
  
  
  2. void traversal(TreeNode* cur, int val)
    3.

沒有返回值，需要記錄上一個節(jié)點(parent)，遇到空節(jié)點了，就讓parent左孩子或者右孩子指向新插入的節(jié)點。然后結(jié)束遞歸。

代碼如下：

 
 
 
 
    
  
  
  
  
  1. class Solution {
    2. 
  
  
  
  
  2. private:
    3. 
  
  
  
  
  3.     TreeNode* parent;
    4. 
  
  
  
  
  4.     void traversal(TreeNode* cur, int val) {
    5. 
  
  
  
  
  5.         if (cur == NULL) {
    6. 
  
  
  
  
  6.             TreeNode* node = new TreeNode(val);
    7. 
  
  
  
  
  7.             if (val > parent->val) parent->right = node;
    8. 
  
  
  
  
  8.             else parent->left = node;
    9. 
  
  
  
  
  9.             return;
    10. 
  
  
  
  
  10.         }
    11. 
  
  
  
  
  11.         parent = cur;
    12. 
  
  
  
  
  12.         if (cur->val > val) traversal(cur->left, val);
    13. 
  
  
  
  
  13.         if (cur->val < val) traversal(cur->right, val);
    14. 
  
  
  
  
  14.         return;
    15. 
  
  
  
  
  15.     }
    16. 
  
  
  
  
  16. 
  
  
  
  
  17. public:
    18. 
  
  
  
  
  18.     TreeNode* insertIntoBST(TreeNode* root, int val) {
    19. 
  
  
  
  
  19.         parent = new TreeNode(0);
    20. 
  
  
  
  
  20.         if (root == NULL) {
    21. 
  
  
  
  
  21.             root = new TreeNode(val);
    22. 
  
  
  
  
  22.         }
    23. 
  
  
  
  
  23.         traversal(root, val);
    24. 
  
  
  
  
  24.         return root;
    25. 
  
  
  
  
  25.     }
    26. 
  
  
  
  
  26. };
    27.

可以看出還是麻煩一些的。

我之所以舉這個例子，是想說明通過遞歸函數(shù)的返回值完成父子節(jié)點的賦值是可以帶來便利的。

網(wǎng)上千變一律的代碼，可能會誤導(dǎo)大家認為通過遞歸函數(shù)返回節(jié)點 這樣的寫法是天經(jīng)地義，其實這里是有優(yōu)化的!

迭代

再來看看迭代法，對二叉搜索樹迭代寫法不熟悉，可以看這篇：二叉樹：二叉搜索樹登場!

在迭代法遍歷的過程中，需要記錄一下當(dāng)前遍歷的節(jié)點的父節(jié)點，這樣才能做插入節(jié)點的操作。

在530.二叉搜索樹的最小絕對差和501.二叉搜索樹中的眾數(shù)中，都是用了記錄pre和cur兩個指針的技巧，本題也是一樣的。

代碼如下：

 
 
 
 
    
  
  
  
  
  1. class Solution {
    2. 
  
  
  
  
  2. public:
    3. 
  
  
  
  
  3.     TreeNode* insertIntoBST(TreeNode* root, int val) {
    4. 
  
  
  
  
  4.         if (root == NULL) {
    5. 
  
  
  
  
  5.             TreeNode* node = new TreeNode(val);
    6. 
  
  
  
  
  6.             return node;
    7. 
  
  
  
  
  7.         }
    8. 
  
  
  
  
  8.         TreeNode* cur = root;
    9. 
  
  
  
  
  9.         TreeNode* parent = root; // 這個很重要，需要記錄上一個節(jié)點，否則無法賦值新節(jié)點
    10. 
  
  
  
  
  10.         while (cur != NULL) {
    11. 
  
  
  
  
  11.             parent = cur;
    12. 
  
  
  
  
  12.             if (cur->val > val) cur = cur->left;
    13. 
  
  
  
  
  13.             else cur = cur->right;
    14. 
  
  
  
  
  14.         }
    15. 
  
  
  
  
  15.         TreeNode* node = new TreeNode(val);
    16. 
  
  
  
  
  16.         if (val < parent->val) parent->left = node;// 此時是用parent節(jié)點的進行賦值
    17. 
  
  
  
  
  17.         else parent->right = node;
    18. 
  
  
  
  
  18.         return root;
    19. 
  
  
  
  
  19.     }
    20. 
  
  
  
  
  20. };
    21.

總結(jié)

首先在二叉搜索樹中的插入操作，大家不用恐懼其重構(gòu)搜索樹，其實根本不用重構(gòu)。

然后在遞歸中，我們重點講了如果通過遞歸函數(shù)的返回值完成新加入節(jié)點和其父節(jié)點的賦值操作，并強調(diào)了搜索樹的有序性。

最后依然給出了迭代的方法，迭代的方法就需要記錄當(dāng)前遍歷節(jié)點的父節(jié)點了，這個和沒有返回值的遞歸函數(shù)實現(xiàn)的代碼邏輯是一樣的。

其他語言版本

Java

 
 
 
 
    
  
  
  
  
  1. class Solution {
    2. 
  
  
  
  
  2.     public TreeNode insertIntoBST(TreeNode root, int val) {
    3. 
  
  
  
  
  3.         if (root == null) return new TreeNode(val);
    4. 
  
  
  
  
  4.         TreeNode newRoot = root;
    5. 
  
  
  
  
  5.         TreeNode pre = root;
    6. 
  
  
  
  
  6.         while (root != null) {
    7. 
  
  
  
  
  7.             pre = root;
    8. 
  
  
  
  
  8.             if (root.val > val) {
    9. 
  
  
  
  
  9.                 root = root.left;
    10. 
  
  
  
  
  10.             } else if (root.val < val) {
    11. 
  
  
  
  
  11.                 root = root.right;
    12. 
  
  
  
  
  12.             }
    13. 
  
  
  
  
  13.         }
    14. 
  
  
  
  
  14.         if (pre.val > val) {
    15. 
  
  
  
  
  15.             pre.left = new TreeNode(val);
    16. 
  
  
  
  
  16.         } else {
    17. 
  
  
  
  
  17.             pre.right = new TreeNode(val);
    18. 
  
  
  
  
  18.         }
    19. 
  
  
  
  
  19. 
  
  
  
  
  20.         return newRoot;
    21. 
  
  
  
  
  21.     }
    22. 
  
  
  
  
  22. }
    23.

遞歸法

 
 
 
 
    
  
  
  
  
  1. class Solution {
    2. 
  
  
  
  
  2.     public TreeNode insertIntoBST(TreeNode root, int val) {
    3. 
  
  
  
  
  3.         return buildTree(root, val);
    4. 
  
  
  
  
  4.     }
    5. 
  
  
  
  
  5. 
  
  
  
  
  6.     public TreeNode buildTree(TreeNode root, int val){
    7. 
  
  
  
  
  7.         if (root == null) // 如果當(dāng)前節(jié)點為空，也就意味著val找到了合適的位置，此時創(chuàng)建節(jié)點直接返回。
    8. 
  
  
  
  
  8.             return new TreeNode(val);
    9. 
  
  
  
  
  9.         if (root.val < val){
    10. 
  
  
  
  
  10.             root.right = buildTree(root.right, val); // 遞歸創(chuàng)建右子樹
    11. 
  
  
  
  
  11.         }else if (root.val > val){
    12. 
  
  
  
  
  12.             root.left = buildTree(root.left, val); // 遞歸創(chuàng)建左子樹
    13. 
  
  
  
  
  13.         }
    14. 
  
  
  
  
  14.         return root;
    15. 
  
  
  
  
  15.     }
    16. 
  
  
  
  
  16. }
    17.

Python

遞歸法- 有返回值

 
 
 
 
    
  
  
  
  
  1. class Solution:
    2. 
  
  
  
  
  2.     def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
    3. 
  
  
  
  
  3.         if root is None:
    4. 
  
  
  
  
  4.             return TreeNode(val) # 如果當(dāng)前節(jié)點為空，也就意味著val找到了合適的位置，此時創(chuàng)建節(jié)點直接返回。
    5. 
  
  
  
  
  5.         if root.val < val:
    6. 
  
  
  
  
  6.             root.right = self.insertIntoBST(root.right, val) # 遞歸創(chuàng)建右子樹
    7. 
  
  
  
  
  7.         if root.val > val:
    8. 
  
  
  
  
  8.             root.left = self.insertIntoBST(root.left, val) # 遞歸創(chuàng)建左子樹
    9. 
  
  
  
  
  9.         return root
    10.

遞歸法- 無返回值

 
 
 
 
    
  
  
  
  
  1. class Solution:
    2. 
  
  
  
  
  2.     def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
    3. 
  
  
  
  
  3.         if not root:
    4. 
  
  
  
  
  4.             return TreeNode(val)
    5. 
  
  
  
  
  5.         parent = None
    6. 
  
  
  
  
  6.         def __traverse(cur: TreeNode, val: int) -> None:
    7. 
  
  
  
  
  7.             # 在函數(shù)運行的同時把新節(jié)點插入到該被插入的地方.
    8. 
  
  
  
  
  8.             nonlocal parent
    9. 
  
  
  
  
  9.             if not cur:
    10. 
  
  
  
  
  10.                 new_node = TreeNode(val)
    11. 
  
  
  
  
  11.                 if parent.val < val:
    12. 
  
  
  
  
  12.                     parent.right = new_node
    13. 
  
  
  
  
  13.                 else:
    14. 
  
  
  
  
  14.                     parent.left = new_node
    15. 
  
  
  
  
  15.                 return
    16. 
  
  
  
  
  16. 
  
  
  
  
  17.             parent = cur # 重點: parent的作用只有運行到上面if not cur:才會發(fā)揮出來.
    18. 
  
  
  
  
  18.             if cur.val < val:
    19. 
  
  
  
  
  19.                 __traverse(cur.right, val)
    20. 
  
  
  
  
  20.             else:
    21. 
  
  
  
  
  21.                 __traverse(cur.left, val)
    22. 
  
  
  
  
  22.             return
    23. 
  
  
  
  
  23.         __traverse(root, val)
    24. 
  
  
  
  
  24.         return root
    25.

迭代法與無返回值的遞歸函數(shù)的思路大體一致

 
 
 
 
    
  
  
  
  
  1. class Solution:
    2. 
  
  
  
  
  2.     def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
    3. 
  
  
  
  
  3.         if not root:
    4. 
  
  
  
  
  4.             return TreeNode(val)
    5. 
  
  
  
  
  5.         parent = None
    6. 
  
  
  
  
  6.         cur = root
    7. 
  
  
  
  
  7. 
  
  
  
  
  8.         # 用while循環(huán)不斷地找新節(jié)點的parent
    9. 
  
  
  
  
  9.         while cur:
    10. 
  
  
  
  
  10.             if cur.val < val:
    11. 
  
  
  
  
  11.                 parent = cur
    12. 
  
  
  
  
  12.                 cur = cur.right
    13. 
  
  
  
  
  13.             elif cur.val > val:
    14. 
  
  
  
  
  14.                 parent = cur
    15. 
  
  
  
  
  15.                 cur = cur.left
    16. 
  
  
  
  
  16. 
  
  
  
  
  17.         # 運行到這意味著已經(jīng)跳出上面的while循環(huán),
    18. 
  
  
  
  
  18.         # 同時意味著新節(jié)點的parent已經(jīng)被找到.
    19. 
  
  
  
  
  19.         # parent已被找到, 新節(jié)點已經(jīng)ready. 把兩個節(jié)點黏在一起就好了.
    20. 
  
  
  
  
  20.         if parent.val > val:
    21. 
  
  
  
  
  21.             parent.left = TreeNode(val)
    22. 
  
  
  
  
  22.         else:
    23. 
  
  
  
  
  23.             parent.right = TreeNode(val)
    24. 
  
  
  
  
  24. 
  
  
  
  
  25.         return root
    26.

當(dāng)前名稱：聊聊二叉搜索樹中的插入操作
當(dāng)前鏈接：http://uogjgqi.cn/article/dpisjdi.html
掃二維碼與項目經(jīng)理溝通

我們在微信上24小時期待你的聲音

解答本文疑問/技術(shù)咨詢/運營咨詢/技術(shù)建議/互聯(lián)網(wǎng)交流