聊聊二叉搜索樹中的插入操作
二叉搜索樹中的插入操作
題目鏈接：https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/
給定二叉搜索樹(BST)的根節(jié)點(diǎn)和要插入樹中的值，將值插入二叉搜索樹。返回插入后二叉搜索樹的根節(jié)點(diǎn)。輸入數(shù)據(jù)保證，新值和原始二叉搜索樹中的任意節(jié)點(diǎn)值都不同。
注意，可能存在多種有效的插入方式，只要樹在插入后仍保持為二叉搜索樹即可。你可以返回任意有效的結(jié)果。
提示：
- 給定的樹上的節(jié)點(diǎn)數(shù)介于 0 和 10^4 之間
- 每個(gè)節(jié)點(diǎn)都有一個(gè)唯一整數(shù)值，取值范圍從 0 到 10^8
- -10^8 <= val <= 10^8
- 新值和原始二叉搜索樹中的任意節(jié)點(diǎn)值都不同
思路
其實(shí)這道題目其實(shí)是一道簡單題目，但是題目中的提示：有多種有效的插入方式，還可以重構(gòu)二叉搜索樹，一下子嚇退了不少人，瞬間感覺題目復(fù)雜了很多。
其實(shí)可以不考慮題目中提示所說的改變樹的結(jié)構(gòu)的插入方式。
如下演示視頻中可以看出：只要按照二叉搜索樹的規(guī)則去遍歷，遇到空節(jié)點(diǎn)就插入節(jié)點(diǎn)就可以了。
二叉搜索樹中的插入操作
例如插入元素10 ，需要找到末尾節(jié)點(diǎn)插入便可，一樣的道理來插入元素15，插入元素0，插入元素6，需要調(diào)整二叉樹的結(jié)構(gòu)么?并不需要。。
只要遍歷二叉搜索樹，找到空節(jié)點(diǎn) 插入元素就可以了，那么這道題其實(shí)就簡單了。
接下來就是遍歷二叉搜索樹的過程了。
遞歸
遞歸三部曲：
- 確定遞歸函數(shù)參數(shù)以及返回值
參數(shù)就是根節(jié)點(diǎn)指針，以及要插入元素，這里遞歸函數(shù)要不要有返回值呢?
可以有，也可以沒有，但遞歸函數(shù)如果沒有返回值的話，實(shí)現(xiàn)是比較麻煩的，下面也會給出其具體實(shí)現(xiàn)代碼。
有返回值的話，可以利用返回值完成新加入的節(jié)點(diǎn)與其父節(jié)點(diǎn)的賦值操作。(下面會進(jìn)一步解釋)
遞歸函數(shù)的返回類型為節(jié)點(diǎn)類型TreeNode * 。
代碼如下：
- TreeNode* insertIntoBST(TreeNode* root, int val)
- 確定終止條件
終止條件就是找到遍歷的節(jié)點(diǎn)為null的時(shí)候，就是要插入節(jié)點(diǎn)的位置了，并把插入的節(jié)點(diǎn)返回。
代碼如下：
- if (root == NULL) {
- TreeNode* node = new TreeNode(val);
- return node;
- }
這里把添加的節(jié)點(diǎn)返回給上一層，就完成了父子節(jié)點(diǎn)的賦值操作了，詳細(xì)再往下看。
- 確定單層遞歸的邏輯
此時(shí)要明確，需要遍歷整棵樹么?
別忘了這是搜索樹，遍歷整顆搜索樹簡直是對搜索樹的侮辱，哈哈。
搜索樹是有方向了，可以根據(jù)插入元素的數(shù)值，決定遞歸方向。
代碼如下：
- if (root->val > val) root->left = insertIntoBST(root->left, val);
- if (root->val < val) root->right = insertIntoBST(root->right, val);
- return root;
到這里，大家應(yīng)該能感受到，如何通過遞歸函數(shù)返回值完成了新加入節(jié)點(diǎn)的父子關(guān)系賦值操作了，下一層將加入節(jié)點(diǎn)返回，本層用root->left或者root->right將其接住。
整體代碼如下：
- class Solution {
- public:
- TreeNode* insertIntoBST(TreeNode* root, int val) {
- if (root == NULL) {
- TreeNode* node = new TreeNode(val);
- return node;
- }
- if (root->val > val) root->left = insertIntoBST(root->left, val);
- if (root->val < val) root->right = insertIntoBST(root->right, val);
- return root;
- }
- };
可以看出代碼并不復(fù)雜。
剛剛說了遞歸函數(shù)不用返回值也可以，找到插入的節(jié)點(diǎn)位置，直接讓其父節(jié)點(diǎn)指向插入節(jié)點(diǎn)，結(jié)束遞歸，也是可以的。
那么遞歸函數(shù)定義如下：
- TreeNode* parent; // 記錄遍歷節(jié)點(diǎn)的父節(jié)點(diǎn)
- void traversal(TreeNode* cur, int val)
沒有返回值，需要記錄上一個(gè)節(jié)點(diǎn)(parent)，遇到空節(jié)點(diǎn)了，就讓parent左孩子或者右孩子指向新插入的節(jié)點(diǎn)。然后結(jié)束遞歸。
代碼如下：
- class Solution {
- private:
- TreeNode* parent;
- void traversal(TreeNode* cur, int val) {
- if (cur == NULL) {
- TreeNode* node = new TreeNode(val);
- if (val > parent->val) parent->right = node;
- else parent->left = node;
- return;
- }
- parent = cur;
- if (cur->val > val) traversal(cur->left, val);
- if (cur->val < val) traversal(cur->right, val);
- return;
- }
- public:
- TreeNode* insertIntoBST(TreeNode* root, int val) {
- parent = new TreeNode(0);
- if (root == NULL) {
- root = new TreeNode(val);
- }
- traversal(root, val);
- return root;
- }
- };
可以看出還是麻煩一些的。
我之所以舉這個(gè)例子，是想說明通過遞歸函數(shù)的返回值完成父子節(jié)點(diǎn)的賦值是可以帶來便利的。
網(wǎng)上千變一律的代碼，可能會誤導(dǎo)大家認(rèn)為通過遞歸函數(shù)返回節(jié)點(diǎn) 這樣的寫法是天經(jīng)地義，其實(shí)這里是有優(yōu)化的!
迭代
再來看看迭代法，對二叉搜索樹迭代寫法不熟悉，可以看這篇：二叉樹：二叉搜索樹登場!
在迭代法遍歷的過程中，需要記錄一下當(dāng)前遍歷的節(jié)點(diǎn)的父節(jié)點(diǎn)，這樣才能做插入節(jié)點(diǎn)的操作。
在530.二叉搜索樹的最小絕對差和501.二叉搜索樹中的眾數(shù)中，都是用了記錄pre和cur兩個(gè)指針的技巧，本題也是一樣的。
代碼如下：
- class Solution {
- public:
- TreeNode* insertIntoBST(TreeNode* root, int val) {
- if (root == NULL) {
- TreeNode* node = new TreeNode(val);
- return node;
- }
- TreeNode* cur = root;
- TreeNode* parent = root; // 這個(gè)很重要，需要記錄上一個(gè)節(jié)點(diǎn)，否則無法賦值新節(jié)點(diǎn)
- while (cur != NULL) {
- parent = cur;
- if (cur->val > val) cur = cur->left;
- else cur = cur->right;
- }
- TreeNode* node = new TreeNode(val);
- if (val < parent->val) parent->left = node;// 此時(shí)是用parent節(jié)點(diǎn)的進(jìn)行賦值
- else parent->right = node;
- return root;
- }
- };
總結(jié)
首先在二叉搜索樹中的插入操作，大家不用恐懼其重構(gòu)搜索樹，其實(shí)根本不用重構(gòu)。
然后在遞歸中，我們重點(diǎn)講了如果通過遞歸函數(shù)的返回值完成新加入節(jié)點(diǎn)和其父節(jié)點(diǎn)的賦值操作，并強(qiáng)調(diào)了搜索樹的有序性。
最后依然給出了迭代的方法，迭代的方法就需要記錄當(dāng)前遍歷節(jié)點(diǎn)的父節(jié)點(diǎn)了，這個(gè)和沒有返回值的遞歸函數(shù)實(shí)現(xiàn)的代碼邏輯是一樣的。
其他語言版本
Java
- class Solution {
- public TreeNode insertIntoBST(TreeNode root, int val) {
- if (root == null) return new TreeNode(val);
- TreeNode newRoot = root;
- TreeNode pre = root;
- while (root != null) {
- pre = root;
- if (root.val > val) {
- root = root.left;
- } else if (root.val < val) {
- root = root.right;
- }
- }
- if (pre.val > val) {
- pre.left = new TreeNode(val);
- } else {
- pre.right = new TreeNode(val);
- }
- return newRoot;
- }
- }
遞歸法
- class Solution {
- public TreeNode insertIntoBST(TreeNode root, int val) {
- return buildTree(root, val);
- }
- public TreeNode buildTree(TreeNode root, int val){
- if (root == null) // 如果當(dāng)前節(jié)點(diǎn)為空，也就意味著val找到了合適的位置，此時(shí)創(chuàng)建節(jié)點(diǎn)直接返回。
- return new TreeNode(val);
- if (root.val < val){
- root.right = buildTree(root.right, val); // 遞歸創(chuàng)建右子樹
- }else if (root.val > val){
- root.left = buildTree(root.left, val); // 遞歸創(chuàng)建左子樹
- }
- return root;
- }
- }
Python
遞歸法 - 有返回值
- class Solution:
- def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
- if root is None:
- return TreeNode(val) # 如果當(dāng)前節(jié)點(diǎn)為空，也就意味著val找到了合適的位置，此時(shí)創(chuàng)建節(jié)點(diǎn)直接返回。
- if root.val < val:
- root.right = self.insertIntoBST(root.right, val) # 遞歸創(chuàng)建右子樹
- if root.val > val:
- root.left = self.insertIntoBST(root.left, val) # 遞歸創(chuàng)建左子樹
- return root
遞歸法 - 無返回值
- class Solution:
- def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
- if not root:
- return TreeNode(val)
- parent = None
- def __traverse(cur: TreeNode, val: int) -> None:
- # 在函數(shù)運(yùn)行的同時(shí)把新節(jié)點(diǎn)插入到該被插入的地方.
- nonlocal parent
- if not cur:
- new_node = TreeNode(val)
- if parent.val < val:
- parent.right = new_node
- else:
- parent.left = new_node
- return
- parent = cur # 重點(diǎn): parent的作用只有運(yùn)行到上面if not cur:才會發(fā)揮出來.
- if cur.val < val:
- __traverse(cur.right, val)
- else:
- __traverse(cur.left, val)
- return
- __traverse(root, val)
- return root
迭代法與無返回值的遞歸函數(shù)的思路大體一致
- class Solution:
- def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
- if not root:
- return TreeNode(val)
- parent = None
- cur = root
- # 用while循環(huán)不斷地找新節(jié)點(diǎn)的parent
- while cur:
- if cur.val < val:
- parent = cur
- cur = cur.right
- elif cur.val > val:
- parent = cur
- cur = cur.left
- # 運(yùn)行到這意味著已經(jīng)跳出上面的while循環(huán),
- # 同時(shí)意味著新節(jié)點(diǎn)的parent已經(jīng)被找到.
- # parent已被找到, 新節(jié)點(diǎn)已經(jīng)ready. 把兩個(gè)節(jié)點(diǎn)黏在一起就好了.
- if parent.val > val:
- parent.left = TreeNode(val)
- else:
- parent.right = TreeNode(val)
- return root
