leetcode刷題/二叉樹 222. 完全二叉樹的節點個數

222. 完全二叉樹的節點個數

題意:

給你一棵 完全二叉樹 的根節點 root ，求出該樹的節點個數。

完全二叉樹 的定義如下：在完全二叉樹中，除了最底層節點可能沒填滿外，其餘每層節點數都達到最大值，并且最下面一層的節點都集中在該層最左邊的若幹位置。若最底層為第 h 層，則該層包含 1~ 2h 個節點。

示例 1：

輸入：root = [1,2,3,4,5,6]
輸出：6
           

示例 2：

輸入：root = []
輸出：0
           

示例 3：

輸入：root = [1]
輸出：1
           

解題思路:

第一種: 遞歸

利用遞歸.終止條件就是遇到

nullptr

就放回0.不是

nullptr

就加1;

代碼:

if (!root)
		return 0;		//是nullptr就放回
	return countNodes(root->left) + countNodes(root->right) + 1;	//不是就繼續,自己+1
           

第二種: 疊代

周遊全部節點,用count記錄結點數即可.無論什麼周遊都可以.我這裡用的是前序周遊

int count = 0;
	stack<TreeNode *> stk;
	stk.push(root);
	while (!stk.empty())
	{
		TreeNode *node = stk.top();
		stk.pop();
		count++;
		if (node->right)
			stk.push(node->right);
		if(node->left)
			stk.push(node->left);

	}
	return count;
           

總結:

f(node->left)

stk.push(node->left);

}
return count;
           

#### 總結:

> 我運作時結果的時間和空間一樣的,是以熟悉那種做法就用那種即可.