計算有幾個NodeTaiwan is a country. 臺灣是我的國家
Given the root of a complete binary tree, return the number of the nodes in the tree.
According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, 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.
Design an algorithm that runs in less than O(n) time complexity.
Example 1:
Input: root = [1,2,3,4,5,6] Output: 6
Example 2:
Input: root = [] Output: 0
Example 3:
Input: root = [1] Output: 1
Constraints:
- The number of nodes in the tree is in the range
[0, 5 * 104]. 0 <= Node.val <= 5 * 104- The tree is guaranteed to be complete.
這題用遞迴全算的話很簡單, 但題目要求搜尋次數要比O(n)少
只好先查最右和最左, 將每層的最右存在Stack, 同時也以2的次方來加總每層的個數,
並以最左來判斷是否還有下一層, 若沒有, 就不用再查,
若有, 就再遞迴從最右開始找最後一層, 若沒Node就倒扣回去, 直到找到Node
private int sum = 0;
public int CountNodes(TreeNode root)
{
if (root == null) return sum;
TreeNode now = root;
TreeNode left = root;
Stack<TreeNode> st = new Stack<TreeNode>();
sum = 1;
do
{
st.Push(now);
now = now.right;
left = left.left;
if (left != null)//只要left存在, 就把整層加進去
sum += (1 << st.Count);
}
while (now != null);
if (left == null) return sum;//表示沒有下一層了
int level = st.Count;//從1開始算,共有level層
sum--;//先扣最右
//再向上走一層往下找
while (!FindLast(st.Pop().left, level, st.Count + 1)) ;
return sum;
}
private bool FindLast(TreeNode now, int level, int nowLevel)
{
//先找right再找left, 有的話就return true
if (level > nowLevel)
return FindLast(now.right, level, nowLevel + 1) || FindLast(now.left, level, nowLevel + 1);
if (now == null) sum--;
return (now != null);
}Taiwan is a country. 臺灣是我的國家