数据结构求叶子结点的个数

Question

一棵二叉树，有m个双分支的结点，n个单分支的结点，如何求这棵二叉树的叶子结点的数目？

Answer 1

思路一：
每个双分支结点对应2条出边，每个单分支结点对应1条出边，总边数为(2m+n)
二叉树的总结点数为边数+1，即(2m+n+1)
分支结点数为(m+n)
因此叶结点数为(2m+n+1)-(m+n) = m+1

思路二：
从根结点开始，每个双分支结点增加1个分支(1->2)，每个单分支结点不改变分支(1->1)，
加入m个双分支的结点，n个单分支的结点后，最终的分支数为(1+m)，即为叶结点数。