[LeetCode] 222. Count Complete Tree Nodes

轉自LeetCode

Given a complete binary tree, count the number of nodes.

Note:

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.

Example:

Input: 
    1
   / \
  2   3
 / \  /
4  5 6

Output: 6

<Solution>

想法如下

• 這題必須利用 complete binary tree 的特性去解，才不會 TLE

• 關鍵在於，最右邊那個節點，可能有，可能沒有

• 如果最右邊的節點存在，那麼答案就是 (2^h) - 1 個節點

• 如果最右邊的節點不存在，那個答案就是目前這個節點，加上左子樹的節點和右子樹的節點， 1 + countNodes(root.left) + countNodes(root.right)

code如下(參考解法)

Java

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	public int countNodes(TreeNode root) {
	if(root == null) {
	return 0;
	}
	int h = 0;
	TreeNode left = root, right = root;
	while(right != null) {
	left = left.left;
	right = right.right;
	++h;
	}
	if(left == null) {
	return (1 << h) - 1;
	}
	return 1 + countNodes(root.left) + countNodes(root.right);
	}
	}

view raw countNodes.java hosted with ❤ by GitHub