6.二叉樹.題目3

題目
- 17.二叉搜索樹中的眾數
- 18.二叉樹的最近公共祖先
- 19.二叉樹搜索樹的最近公共祖先
- 20.二叉搜索樹中的插入操作。
- - 普通二叉樹的刪除方式
- 21.刪除二叉搜索樹中的節點
- 22.修剪二叉樹
- 23.將有序數組轉化為二叉搜索樹
- 24.把二叉搜索樹轉化為累加樹
總結

題目

17.二叉搜索樹中的眾數

（題目鏈接）
給定一個有相同值的二叉搜索樹（BST），找出 BST 中的所有眾數（出現頻率最高的元素。
首先如果不是二叉搜索樹的話，應該怎么解題，是二叉搜索樹，又應該如何解題，兩種方式做一個比較，可以加深大家對二叉樹的理解。

如果不是二叉搜索樹：最直觀的辦法是先將樹遍歷一遍，再使用map統計頻率，然后把頻率排序，最后取高頻的元素的集合

/* 表示在排序時，a應該排在b前面。因此，當我們使用這個函數對vector<pair<int, int>>進行排序時，頻率最高的元素會被放在前面*/
bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second;
}vector<int> findMode(TreeNode* root) {unordered_map<int, int> map; // key:元素，value:出現頻率vector<int> result;if (root == NULL) return result;// 遍歷樹，并將樹出現頻率統計在map中searchBST(root, map);vector<pair<int, int>> vec(map.begin(), map.end());sort(vec.begin(), vec.end(), cmp); // 給頻率排個序result.push_back(vec[0].first);for (int i = 1; i < vec.size(); i++) {// 取最高的放到result數組中if (vec[i].second == vec[0].second) result.push_back(vec[i].first);else break;}return result;}

如果是二叉搜索樹：將二叉搜索樹通過中序遍歷展開為遞增序列，然后通過一次遍歷即可把眾數放入數組res中。使用了pre指針和cur指針的技巧。使用一個指針指向前一個節點，這樣每次cur（當前節點）才能和pre（前一個節點）作比較。

private:int maxcount = 0;int count = 0;TreeNode* pre = nullptr;std::vector<int> res;void backtracking(TreeNode* root){if(root==nullptr) return;backtracking(root->left);// 根據pre，root修改計數countif(pre==nullptr) count=1;else if(pre->val==root->val) count++;else count=1; pre = root; // 更新pre的指針位置if(count==maxcount) res.push_back(root->val);if(count>maxcount){res.clear();maxcount = count;res.push_back(root->val);}backtracking(root->right);return;}
public:vector<int> findMode(TreeNode* root) {res.clear();backtracking(root);return res;}

18.二叉樹的最近公共祖先

（題目鏈接）
給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。最近公共祖先的定義：對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。說明：所有節點的值都是唯一的；p、q 為不同節點且均存在于給定的二叉樹中。
尋找最近公共祖先節點，需要我們從二叉樹的底部往頂部進行處理，這就需要使用后序遍歷的方法（左右上）
終止條件：當cur==nullptr，以及當cur==p || q說明也遍歷到了目標節點，到達葉子節點位置時結束
確定單層遞歸邏輯-本題的遞歸函數有返回值，因為回溯的過程需要遞歸函數的返回值做判斷，而遞歸函數有返回值就是要遍歷某一條邊，但有返回值也要看如何處理返回值。

// 搜索一條邊
if (遞歸函數(root->left)) return ;
if (遞歸函數(root->right)) return ;
// 搜索整個樹
left = 遞歸函數(root->left);  // 左
right = 遞歸函數(root->right); // 右
left與right的邏輯處理;         // 中

在遞歸函數有返回值的情況下：如果要搜索一條邊，遞歸函數返回值不為空的時候，立刻返回；如果搜索整個樹，直接用一個變量left、right接住返回值，這個left、right后序還有邏輯處理的需要，也就是后序遍歷中處理中間節點的邏輯（也是回溯）。
在這里插入圖片描述

    TreeNode* backtracking(TreeNode* root, TreeNode* p, TreeNode* q){// 終止條件if(root==nullptr) return root;if(root==p || root==q) return root;TreeNode* left = backtracking(root->left, p, q);TreeNode* right = backtracking(root->right, p, q);// 后序遍歷，中序需要左，右子樹的值進行判斷if(left!=nullptr && right!=nullptr) return root;else if(left==nullptr && right!=nullptr) return right;else if(left!=nullptr && right==nullptr) return left;else return nullptr;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {return backtracking(root, p, q);}

19.二叉樹搜索樹的最近公共祖先

（題目鏈接）
因為是有序樹，所以如果中間節點是 q 和 p 的公共祖先，那么中節點的數組一定是在 [p, q]區間的。那么只要從上到下去遍歷，遇到 cur節點是數值在[p, q]區間中則一定可以說明該節點cur就是p 和 q的公共祖先，那么該如何判斷是最近祖先？
在這里插入圖片描述
跟據以上的例子，所以當我們從上向下去遞歸遍歷，第一次遇到 cur節點是數值在[q, p]區間中，那么cur就是 q和p的最近公共祖先。

    TreeNode* backtracking(TreeNode* root, TreeNode* p, TreeNode* q){if(root==nullptr) return root;if(root->val>p->val && root->val>q->val){TreeNode* left = backtracking(root->left, p, q);if(left!=nullptr) return left;}if(root->val<p->val && root->val<q->val){TreeNode* right = backtracking(root->right, p, q);if(right!=nullptr) return right;}return root;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {return backtracking(root, p, q);}

20.二叉搜索樹中的插入操作。

（題目鏈接）
給定二叉搜索樹（BST）的根節點和要插入樹中的值，將值插入二叉搜索樹。返回插入后二叉搜索樹的根節點。輸入數據保證：新值和原始二叉搜索樹中的任意節點值都不同。其實只要遍歷二叉搜索樹，找到空節點插入元素就可以了，那么這道題其實就簡單了。
遞歸函數設置返回值，可以利用返回值完成新加入的節點與其父節點的賦值操作；
終止條件：當cur==nullptr，到達葉子節點位置時結束，就是要插入新節點的位置，并把插入的節點返回。
單層遞歸的邏輯：二叉搜索樹的遞歸方向，根據val值與root->val的比值大小

	// 遞歸函數設置返回值，用于終止條件時新節點的賦值TreeNode* insertIntoBST(TreeNode* root, int val) {if(root==nullptr){TreeNode* node = new TreeNode(val);return node;}if(val>root->val) root->right = insertIntoBST(root->right, val); //在終止條件時完成對root的插入新子節點if(val<root->val) root->left = insertIntoBST(root->left, val);return root;}

當然該遞歸函數也可不設置返回值，需要記錄每次遞歸前上一個節點（parent），遇到空節點了，就讓parent左孩子或者右孩子指向新插入的節點。然后結束遞歸。

	// 遞歸函數不設置返回值，需要外部指針記錄父節點TreeNode* par;void backtracking(TreeNode* root, int val){if(root==nullptr){TreeNode* node = new TreeNode(val);if(val>par->val) par->right = node;else par->left = node;return;}par = root; //不需要回溯，只需記錄每次遞歸的父節點if(val>root->val) backtracking(root->right, val);if(val<root->val) backtracking(root->left, val);return;}TreeNode* insertIntoBST(TreeNode* root, int val) {par = new TreeNode(val);if(root==nullptr){root = new TreeNode(val);}backtracking(root, val);return root;}

普通二叉樹的刪除方式

對于沒有數值大小排序需要的普通二叉樹，通用的二叉樹的刪除方法。主要分為兩個步驟

和目標節點的右子樹最左面節點交換
直接用nullptr覆蓋

	// 比較繞，需要思考以西。TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr) return root;if (root->val == key) {if (root->right == nullptr) { // 這里第二次操作目標值：最終刪除的作用return root->left;}TreeNode *cur = root->right;while (cur->left) {cur = cur->left;}swap(root->val, cur->val); // 這里第一次操作目標值：交換目標值其右子樹最左面節點。}root->left = deleteNode(root->left, key);root->right = deleteNode(root->right, key);return root;}

21.刪除二叉搜索樹中的節點

（題目鏈接）
給定一個二叉搜索樹的根節點 root 和一個值 key，刪除二叉搜索樹中的 key 對應的節點，并保證二叉搜索樹的性質不變。刪除節點分為兩個步驟：1.找到要刪除的節點 2.刪除元素。但搜索二叉樹的刪除節點要比普通的二叉樹復雜多，因此涉及要刪除節點的子樹的重新排序的問題。
遞歸函數參數，返回值：
終止條件：當cur==nullptr，到達葉子節點位置時結束
每層遞歸邏輯：得分情況處理（處理是在父節點parent層處理的）

根據key，沒有找到要刪除的節點，不用處理，遍歷到空節點就返回了
左右子節點都為空，則直接刪除該節點
左節點為空，右節點非空，刪除該節點，右節點補位
右節點為空，左節點非空，刪除該節點，左節點補位
左右節點為非空，則將刪除節點的左子樹頭結點（左孩子）放到刪除節點的右子樹的最左面節點的左孩子上，返回刪除節點右孩子為新的根節點。(這樣操作的目的是二叉搜索樹的右子樹的元素是均大于左子樹的元素的，而右子樹的的最小值必在最深的左葉子節點處，因此若刪除父節點，則可以很自然地把左子樹的頭節點接到右子樹的最深左葉子節點的left端)

在這里插入圖片描述

    TreeNode* deleteNode(TreeNode* root, int key) {if(root==nullptr) return root;// 處理節點 因為遞歸函數有返回值-實現父節點修改處理if(root->val == key){if(root->left==nullptr && root->right==nullptr){delete root;return nullptr;}else if(root->left==nullptr && root->right!=nullptr){auto node = root->right;delete root;return node;}else if(root->right==nullptr && root->left!=nullptr){auto node = root->left;delete root;return node;}else{auto node = root->right;while(node->left!=nullptr) node=node->left;node->left = root->left;TreeNode* tmp = root;root = root->right;delete tmp; //釋放原本root的內存return root;}}//指定遞歸的方向if(root->val>key) root->left = deleteNode(root->left, key);if(root->val<key) root->right = deleteNode(root->right, key);return root;}

22.修剪二叉樹

（題目鏈接）
給定一個二叉搜索樹，同時給定最小邊界L 和最大邊界 R。通過修剪二叉搜索樹，使得所有節點的值在[L, R]中 (R>=L)。可能需要改變樹的根節點，所以結果應當返回修剪好的二叉搜索樹的新的根節點。
遞歸函數確定參數，返回值：有返回值，更方便，可以通過遞歸函數的返回值來移除節點（返回值是為了這一點服務的）；
終止條件：當root==nullptr
單層遞歸的邏輯：1. （本層）如果root（當前節點）的元素小于low的數值，那么應該遞歸右子樹，并返回右子樹符合條件的頭結點；如果root(當前節點)的元素大于high的，那么應該遞歸左子樹，并返回左子樹符合條件的頭結點。2.（下一層）接下來要將下一層處理完左子樹的結果賦給root->left，處理完右子樹的結果賦給root->right。

    TreeNode* trimBST(TreeNode* root, int low, int high) {if(root==nullptr) return nullptr;// 處理節點，相當于局部調整root節點附近if(root->val<low){TreeNode* right = trimBST(root->right, low, high);return right;}if(root->val>high){TreeNode* left = trimBST(root->left, low, high);return left;}root->left = trimBST(root->left, low, high);root->right = trimBST(root->right, low, high);return root;}

23.將有序數組轉化為二叉搜索樹

（題目鏈接）
將一個按照升序排列的有序數組，轉換為一棵高度平衡二叉搜索樹。高度平衡二叉樹指：一個高度平衡二叉樹是指一個二叉樹每個節點的左右兩個子樹的高度差的絕對值不超過 1。
在這里插入圖片描述
做這道題目需要了解：1.從中序后序遍歷序列構造二叉樹，最大二叉樹，二叉搜索樹中的插入操作；刪除二叉搜索數中的節點。其實數組構造二叉樹，構成平衡樹是自然而然的事情，因為大家默認都是從數組中間位置取值作為節點元素，一般不會隨機取。
本質就是尋找分割點，分割點作為當前節點，然后遞歸左區間和右區間。但數組長度為偶數，中間節點有兩個，取不同的作為根節點，會造成不同的平衡二叉搜索樹。
在這里插入圖片描述
遞歸函數參數和返回值：首先是傳入數組，然后就是左下標left和右下標right；在構造二叉樹的時候盡量不要重新定義左右區間數組，而是用下標來操作原數組，此處定義使用的是左閉右閉區間。
遞歸終止條件：當區間left > right的時候，就是空節點了
確定單層遞歸邏輯：所以可以這么寫：int mid = left + ((right - left) / 2);出于考慮right+left可能會出現越界的問題。取了中間位置，就開始以中間位置的元素構造節點，然后接著劃分區間，root的左孩子接住下一層左區間的構造節點，右孩子接住下一層右區間構造的節點。最后返回root。
遞歸法

    TreeNode* traversal(std::vector<int>& nums, int left, int right){// 切割問題，根據區間下標返回if(left>right) return nullptr;int mid = left + (right-left)/2;TreeNode* root = new TreeNode(nums[mid]);root->left = traversal(nums, left, mid-1);root->right = traversal(nums, mid+1, right);return root; }TreeNode* sortedArrayToBST(vector<int>& nums) {return traversal(nums, 0, nums.size()-1);}

不斷中間分割，然后遞歸處理左區間，右區間，也可以說是分治；這需要應該對通過遞歸函數的返回值來增刪二叉樹很熟悉了，這也是常規操作。

24.把二叉搜索樹轉化為累加樹

（題目鏈接）
給出二叉搜索樹的根節點，該樹的節點值各不相同，請你將其轉換為累加樹（Greater Sum Tree），使每個節點 node 的新值等于原樹中大于或等于 node.val 的值之和。提示：樹中的節點數介于 0 和 104 之間；每個節點的值介于 -104 和 104 之間；樹中的所有值互不相同；給定的樹為二叉搜索樹。
在這里插入圖片描述
從樹中可以看出累加的順序是右中左，所以我們需要反中序遍歷這個二叉樹，然后順序累加就可以了。本題依然需要一個pre指針記錄當前遍歷節點cur的前一個節點，這樣才方便做累加——采用pre指針的題目還有1.搜索樹的最小絕對值差，2.我的眾數
遞歸函數參數和返回值：不需要返回值，只需要使用pre記錄前一個節點的val作累加
終止條件：當cur==nullptr即可終止
單層遞歸的邏輯：遵循右中左遍歷順序，中間節點的操作是賦值為當前值+pre的值，并且更新pre值
遞歸法

    int pre=0;void traversal(TreeNode* root){if(root==nullptr) return;traversal(root->right);root->val += pre;pre = root->val;traversal(root->left);}TreeNode* convertBST(TreeNode* root) {pre = 0;traversal(root);return root;}