二叉樹問題（三）-LeetCode 669、951、662、199、538、236（中序，層次遍歷）
- 2019 年 12 月 24 日
- 筆記
作者：TeddyZhang，公眾號：演算法工程師之路
二叉樹問題（三）：
LeetCode # 669 951 662 199 538 236
1
編程題
【LeetCode #669】修剪二叉搜索樹
給定一個二叉搜索樹，同時給定最小邊界L 和最大邊界 R。通過修剪二叉搜索樹，使得所有節點的值在[L, R]中 (R>=L) 。你可能需要改變樹的根節點，所以結果應當返回修剪好的二叉搜索樹的新的根節點。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* trimBST(TreeNode* root, int L, int R) { if (root == nullptr) return root; // 處理異常節點，將root->right提升為root if (root->val < L) return trimBST(root->right, L, R); if (root->val > R) return trimBST(root->left, L, R); // 處理正常的節點 root->left = trimBST(root->left, L, R); root->right = trimBST(root->right, L, R); return root; } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/trim-a-binary-search-tree
【LeetCode #951】翻轉等價二叉樹
我們可以為二叉樹 T 定義一個翻轉操作，如下所示：選擇任意節點，然後交換它的左子樹和右子樹。 只要經過一定次數的翻轉操作後，能使 X 等於 Y，我們就稱二叉樹 X 翻轉等價於二叉樹 Y。 編寫一個判斷兩個二叉樹是否是翻轉等價的函數。這些樹由根節點 root1 和 root2 給出。
示例： 輸入：root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7] 輸出：true 解釋：We flipped at nodes with values 1, 3, and 5.
解題思路：
由於該二叉樹經過多次翻轉可以重合，因此要麼是一棵樹的左子樹等於另一個的左子樹，或者一棵樹的左子樹等於另一棵樹的右子樹。如果對應根節點不相同，那麼永遠也不會重合，返回false即可。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool flipEquiv(TreeNode* root1, TreeNode* root2) { if (root1 == root2) return true; if (root1 == nullptr && root2 != nullptr) return false; if (root1 != nullptr && root2 == nullptr) return false; if (root1->val != root2->val) return false; return flipEquiv(root1->left, root2->right) && flipEquiv(root1->right, root2->left) || flipEquiv(root1->left, root2->left) && flipEquiv(root1->right, root2->right); } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/flip-equivalent-binary-trees
【LeetCode #662】二叉樹最大寬度
給定一個二叉樹，編寫一個函數來獲取這個樹的最大寬度。樹的寬度是所有層中的最大寬度。這個二叉樹與滿二叉樹（full binary tree）結構相同，但一些節點為空。
每一層的寬度被定義為兩個端點（該層最左和最右的非空節點，兩端點間的null節點也計入長度）之間的長度。
解題思路：
每層的索引值都從1開始，也就是如果某一個節點的索引為i，則其左孩子索引為（2*i – 上層最開始的節點索引），這樣可以重置索引，避免二叉樹節點過多導致索引值溢出。 然後當訪問到最右邊不是nullptr的節點，才進行寬度的計算。注意訪問最右邊不是nullptr節點時，size正好遞減為0.
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int widthOfBinaryTree(TreeNode* root) { using PairNode = pair<TreeNode*, int>; int res = INT_MIN; queue<PairNode> que; que.push(make_pair(root, )); while(!que.empty()) { int size = que.size(); int i = que.front().second; while(size--) { PairNode tmp = que.front(); que.pop(); if (size == ) // 只有size等於0時，才會訪問到每層最右邊不為nullptr的節點，此時計算width res = max(res, tmp.second - i + ); // 每一層都從 1 開始 if (tmp.first->left) que.push(make_pair(tmp.first->left, tmp.second* - i)); if (tmp.first->right) que.push(make_pair(tmp.first->right, tmp.second*+ - i)); } } return res; } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/maximum-width-of-binary-tree
【LeetCode #199】二叉樹的右視圖
給定一棵二叉樹，想像自己站在它的右側，按照從頂部到底部的順序，返回從右側所能看到的節點值。
解題思路：
使用層序遍歷，不同是的，我們需要將每一層的節點從右向左送入隊列中，然後一次處理整個一層數，在處理之前，向vector中壓入第一個節點的值（也就是每層最右邊那一個）。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> rightSideView(TreeNode* root) { vector<int> res; if (root == nullptr) return res; queue<TreeNode*> que; que.push(root); while(!que.empty()) { int size = que.size(); res.push_back(que.front()->val); while(size--){ TreeNode* tmp = que.front(); que.pop(); // 從右向左入隊列 if (tmp->right) que.push(tmp->right); if (tmp->left) que.push(tmp->left); } } return res; } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/binary-tree-right-side-view/
【LeetCode #538】把二叉搜索樹變成累加樹
給定一個二叉搜索樹（Binary Search Tree），把它轉換成為累加樹（Greater Tree)，使得每個節點的值是原來的節點值加上所有大於它的節點值之和。
解題思路：
對於原來的中序遍歷，是：左 –> 根 –> 右，對於這道題目而言，我們需要從右邊開始，然後依次累加並賦值。
(遞歸法)
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int sum = ; TreeNode* convertBST(TreeNode* root) { if (root == nullptr) return nullptr; convertBST(root->right); sum += root->val; root->val = sum; convertBST(root->left); return root; } };
（迭代版）
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int sum = ; TreeNode* convertBST(TreeNode* root) { stack<TreeNode*> sta; TreeNode* cur = root; while(cur != nullptr || !sta.empty()) { if (cur != nullptr) { sta.push(cur); cur = cur->right; // 與之前的中序遍歷正好相反 } else { cur = sta.top(); sta.pop(); sum += cur->val; cur->val = sum; cur = cur->left; } } return root; } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/convert-bst-to-greater-tree
【LeetCode #236】二叉樹的最近公共祖先
給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。
百度百科中最近公共祖先的定義為：「對於有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度儘可能大（一個節點也可以是它自己的祖先）。」
解題思路：
首先找出根節點到p, q兩個節點的二叉樹路徑，然後再根據路徑進行匹配，最後一個相同的元素即為公共祖先。 注意路徑的元素為指針（地址）, 由於使用val的話會有衝突的缺點。
class Solution { private: bool dfs(vector<TreeNode*>& path, TreeNode* root, TreeNode* find) { if (root == nullptr) return false; path.push_back(root); if (root == find) { return true; } if (dfs(path, root->left, find)) return true; if (dfs(path, root->right, find)) return true; path.pop_back(); return false; } public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { vector<TreeNode*> ll, rr; if(!dfs(ll, root, p) || !dfs(rr, root, q)) return nullptr; int i = ; for (; i < ll.size() && i < rr.size(); i++) { if (ll[i] != rr[i]) return ll[i-1]; } return ll[i-1]; } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
