推 tzyysang: max_id和node_num可以放在class? 遞迴少傳兩個參數03/15 11:46
也是可以 但沒測過這樣速度差多少
我已經寫習慣不把太多變數丟外面了
※ 編輯: idiont (140.113.229.216 臺灣), 03/15/2023 12:56:20
958. Check Completeness of a Binary Tree
給一棵 binary tree，
問這是否是一棵 complete binary tree，
也就是除了最下面一層以外，深度 h 的節點數量都有 2^h 個節點 (root 的深度為 0)，
並且最下面一層的節點都是往左側靠。
Example 1:
Input: root = [1,2,3,4,5,6]
Output: true
Explanation:
https://assets.leetcode.com/uploads/2018/12/15/complete-binary-tree-1.png
深度 0 有 1 個 node，深度 1 有 2 個 node，最下層 3 個都是往左側靠，符合定義。
Example 2:
Input: root = [1,2,3,4,5,null,7]
Output: false
Explanation:
https://assets.leetcode.com/uploads/2018/12/15/complete-binary-tree-2.png
最下層的 5 跟 7 之間有空隙，所以不是 complete binary tree。
解題思路:
重新幫 node 進行編號，root 為 1，
對於任意一個 node i，left child 編號為 i*2，right child 編號為 i*2+1。
對於一個 n 個 node 的 complete binary tree，node 的編號會落在 [1,n]，
在 DFS 遍歷所有 node 時紀錄總共有多少個 node 以及編號最大值，
編號最大值與 node 數量相等時即說明這是一個 complete binary tree。
因為此題限制 node 數量最多為 100，為了避免編號時 overflow，
若是發現編號大於 100 則可以剪枝並確定這不是棵 complete binary tree。
C++ code:
class Solution {
public:
bool isCompleteTree(TreeNode* root) {
int max_id = 0, node_num = 0;
dfs(root, 1, max_id, node_num);
return max_id == node_num;
}
void dfs(TreeNode *p, int id, int &max_id, int &node_num){
if(!p) return;
max_id = max(max_id, id);
node_num++;
if(max_id > 100) return;
dfs(p->left, id*2, max_id, node_num);
dfs(p->right, id*2+1, max_id, node_num);
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.229.216 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1678851422.A.777.html