推 int0x80: 好強 11/15 12:10
推 pandix: 大師 11/15 14:08
→ NTHUlagka: 大師 11/15 19:48
→ GTR12534: 完全二元樹的左樹沒有一定是滿的吧？ 11/16 04:45
→ Rushia: 欸欸 對欸 有可能也是個完全二元樹 我改一下= = 11/16 09:10
※ 編輯: Rushia (36.231.29.216 臺灣), 11/16/2022 09:12:18
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