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.題目給的測資都是完全二元樹，一個完全二元樹未必是一個完滿二元樹，但是 他的左樹必定是一個完滿二元樹。 3.如果當前的樹是一個完滿二元樹(左樹高=右樹高)直接套公式計算，否則對左樹 和右樹遞迴並+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