程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode222 Count CompleteTree Nodes(計算完全二叉樹的節點數) Java 題解

LeetCode222 Count CompleteTree Nodes(計算完全二叉樹的節點數) Java 題解

編輯:C++入門知識

LeetCode222 Count CompleteTree Nodes(計算完全二叉樹的節點數) Java 題解


題目:

 

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<

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved