Re: [閒聊] 每日LeetCode
222. Count Complete Tree Nodes
給你一個完全二元樹，判斷該二元樹共有幾個節點。
限制：你必須設計一個小於O(n)時間的演算法。
https://assets.leetcode.com/uploads/2021/01/14/complete.jpg
Input: root = [1,2,3,4,5,6]
Output: 6
思路：
1.如果一個樹是一個完滿(full)二元樹，那麼他的節點數量可以直接由高度計算
出來不需遍歷每個節點（2^h-1）
2.如果當前的樹是一個完滿二元樹(左樹高=右樹高)直接套公式計算，否則對左樹
和右樹遞迴並+1(當前節點)，不斷遞迴之後最後一個樹一定是一個完滿樹（只有根）
JavaCode：
----------------------------------------
class Solution {
public int countNodes(TreeNode root) {
int l = leftHeight(root);
int r = rightHeight(root);
if (l == r) {
return (int)Math.pow(2, l) - 1;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
private int leftHeight(TreeNode root) {
if (root == null) {
return 0;
}
return leftHeight(root.left) + 1;
}
private int rightHeight(TreeNode root) {
if (root == null) {
return 0;
}
return rightHeight(root.right) + 1;
}
}
----------------------------------------
芒果假面
--
https://i.imgur.com/sjdGOE3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.80.62 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1668475942.A.E90.html
推
11/15 12:10,
3年前
, 1F
11/15 12:10, 1F
推
11/15 14:08,
3年前
, 2F
11/15 14:08, 2F
→
11/15 19:48,
3年前
, 3F
11/15 19:48, 3F
→
11/16 04:45,
3年前
, 4F
11/16 04:45, 4F
→
11/16 09:10,
3年前
, 5F
11/16 09:10, 5F
※ 編輯: Rushia (36.231.29.216 臺灣), 11/16/2022 09:12:18
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 103 之 719 篇)：