二叉樹問題（二）-LeetCode 965、563、993、958、919（樹深度，層次遍歷）
- 2019 年 12 月 24 日
- 筆記
作者：TeddyZhang，公眾號：算法工程師之路
二叉樹問題（二）：
LeetCode # 965 563 993 958 919
1
編程題
【LeetCode #965】單值二叉樹
如果二叉樹每個節點都具有相同的值，那麼該二叉樹就是單值二叉樹。 只有給定的樹是單值二叉樹時，才返回 true；否則返回 false。
(迭代法，中序遍歷)
class Solution { public: bool isUnivalTree(TreeNode* root) { stack<TreeNode*> sta; TreeNode* pre = nullptr; TreeNode* cur = root; while(cur != nullptr || !sta.empty()) { if(cur != nullptr) { sta.push(cur); cur = cur->left; }else { cur = sta.top(); sta.pop(); if (pre && pre->val != cur->val) { return false; } pre = cur; cur = cur->right; } } return true; } };
(遞歸法)
class Solution { public: bool isUnivalTree(TreeNode* root) { if (root == nullptr) return true; if (root->left && root->left->val != root->val) { return false; } if (root->right && root->right->val != root->val) { return false; } return isUnivalTree(root->left) && isUnivalTree(root->right); } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/univalued-binary-tree/
【LeetCode #563】二叉樹的坡度
給定一個二叉樹，計算整個樹的坡度。
一個樹的節點的坡度定義即為，該節點左子樹的結點之和和右子樹結點之和的差的絕對值。空結點的的坡度是0。 整個樹的坡度就是其所有節點的坡度之和。
示例: 輸入: 1 / 2 3 輸出: 1 解釋: 結點的坡度 2 : 0 結點的坡度 3 : 0 結點的坡度 1 : |2-3| = 1 樹的坡度 : 0 + 0 + 1 = 1
解題思路：
首先我們寫出一個計算一個二叉樹中子樹的節點和的遞歸式子，然後再遞歸參數中使用count來累加兩個子樹節點和的差值，最後返回count即可。注意使用引用傳遞而不是值傳遞。
/** * 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 add(TreeNode* node, int& count) { if(node == nullptr) return ; int left = add(node->left, count); int right = add(node->right, count); count += abs(left - right); return left+right+node->val; } int findTilt(TreeNode* root) { int res = ; add(root, res); return res; } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/binary-tree-tilt
【LeetCode #993】二叉樹的堂兄節點
在二叉樹中，根節點位於深度 0 處，每個深度為 k 的節點的子節點位於深度 k+1 處。 如果二叉樹的兩個節點深度相同，但父節點不同，則它們是一對堂兄弟節點。 我們給出了具有唯一值的二叉樹的根節點 root，以及樹中兩個不同節點的值 x 和 y。 只有與值 x 和 y 對應的節點是堂兄弟節點時，才返回 true。否則，返回 false
解題思路：
使用pair類型儲存對應x節點以及y節點的深度和父節點的值，然後進行比較即可。 注意該二叉樹中的值都是唯一的，沒有重複的。
/** * 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: void find(TreeNode* node, int val, int dep, int par, pair<int, int>& res) { if (node == nullptr) return; if (node->val == val) { res.first = dep; res.second = par; return; } else { find(node->left, val, dep+, node->val, res); find(node->right, val, dep+, node->val, res); } } bool isCousins(TreeNode* root, int x, int y) { pair<int, int> res1, res2; find(root, x, , -1, res1); // 根節點的父節點值設為-1 find(root, y, , -1, res2); return (res1.first == res2.first) && (res1.second != res2.second); } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/cousins-in-binary-tree
【LeetCode #958】二叉樹的完全性檢驗（完全二叉樹）
給定一個二叉樹，確定它是否是一個完全二叉樹。 百度百科中對完全二叉樹的定義如下： 若設二叉樹的深度為 h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層所有的結點都連續集中在最左邊，這就是完全二叉樹。（註：第 h 層可能包含 1~ 2h 個節點。）
解題思路：
使用類似層次遍歷的方法，使用flag標記遇到了nullptr，然後置為true，接着判斷當flag=true時，接下來訪問的節點是否為空，如果都為空，則說明是完全二叉樹，否則不是。 注意：為了將stack中加入nullptr，因此只判斷tmp是否為空即可！
/** * 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 isCompleteTree(TreeNode* root) { bool flag = false; queue<TreeNode*> que; que.push(root); while(!que.empty()) { TreeNode* tmp = que.front(); que.pop(); if (tmp == nullptr) flag = true; if (flag && tmp) return false; // 遇到nullptr，後面都應該是nullptr if (tmp) { // 與層次遍歷不同，只需要判斷tmp是否為nullptr que.push(tmp->left); que.push(tmp->right); } } return true; } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/check-completeness-of-a-binary-tree
【LeetCode #919】完全二叉樹插入器
完全二叉樹是每一層（除最後一層外）都是完全填充（即，結點數達到最大）的，並且所有的結點都儘可能地集中在左側。 設計一個用完全二叉樹初始化的數據結構 CBTInserter，它支持以下幾種操作：
CBTInserter(TreeNode root) 使用頭結點為 root 的給定樹初始化該數據結構； CBTInserter.insert(int v) 將 TreeNode 插入到存在值為 node.val = v 的樹中以使其保持完全二叉樹的狀態，並返回插入的 TreeNode 的父結點的值； CBTInserter.get_root() 將返回樹的頭結點。
解題思路：
LeetCode上的翻譯很爛，簡單來說，就是現在有一顆root為根節點的完全二叉樹，當我們向二叉樹中插入節點的，也應該保證完全二叉樹的性質，這在裏面使用層次遍歷的方法，尋找某個節點的左節點或者右節點為nullptr的節點，定為待插入節點root_. 注意如果向某個節點的右節點插入了一個節點，那麼待插入節點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 CBTInserter { public: queue<TreeNode*> que; // 注意root為一個完全二叉樹 CBTInserter(TreeNode* root) : root_(root), node_(nullptr) { que.push(root_); while(!que.empty()) { TreeNode* tmp = que.front(); que.pop(); if (tmp->left) que.push(tmp->left); if (tmp->right) que.push(tmp->right); if (node_ == nullptr && (tmp->left == nullptr || tmp->right == nullptr)) { node_ = tmp; break; } } } int insert(int v) { TreeNode* newNode = new TreeNode(v); int father = node_->val; if(node_->left == nullptr) node_->left = newNode; else { node_->right = newNode; if (!que.empty()) { node_ = que.front(); que.pop(); } } return father; } TreeNode* get_root() { return root_; } private: TreeNode* node_; // 用來儲存待插入節點的位置 TreeNode* root_; // 用來儲存樹根節點的位置 };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/complete-binary-tree-inserter
