題目:
Given a complete binary tree, count the number of nodes.
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
解題:
如果用常規的解法一個個遍歷,就是O(n)時間復雜度 ,會不通過,這邊就不寫O(n)的代碼了。因為是完全二叉樹,滿二叉樹有一個性質是節點數等於2^h-1,h為高度,所以可以這樣判斷節點的左右高度是不是一樣,如果是一樣說明是滿二叉樹,就可以用剛才的公式,如果左右不相等就遞歸計算左右節點。
代碼:
public static int countNodes(TreeNode root) { if(root==null) return 0; else { int left=getLeftHeight(root); int right=getRightHeight(root); if(left==right) return (1<