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.觀察 complete binary tree 如果 root 是 1 並且 node.val 代表前面有幾個 node 往左子樹走 node.val 會 *2 往右會 *2+1 目標就可以變成想辦法走到最下排最右邊的那個 node 並且邊走邊算 2.要怎麼知道最下最右的 node 在左子樹還是右子樹? 可以用借用 complete binary tree 的性質 用左子樹樹高和右子樹樹高判斷 如果相等就會在右子樹 反之則在左子樹 樹高可以直接走左邊走到底得到 問就是性質 所以流程就是 對每個 node 看 node.left 和 node.right 往左走能走多深 因為右邊一定不會比左邊高 所以可以一起走 看右邊走到底時左邊還有沒有東西 兩個高度一樣就往右 res = res*2+1 反之往左 res = res*2 直到找到最下最右的 node 複雜度是 log(n) 層 * 每層決定要走左右也是 log(n) = O(log(n)^log(n)) 3. Python code: class Solution: def countNodes(self, root: Optional[TreeNode]) -> int: res = 1 if root else 0 node = root while node: L, R = node.left, node.right if not L and not R: break while R: L = L.left R = R.left res = res*2 if L else res*2+1 node = node.left if L else node.right return res 今天沒有龍大 -- 可憐 --
※ 批踢踢實業坊(ptt.cc), 來自: 111.251.212.49 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1668497274.A.342.html

→ steven183: 大師 11/15 15:35