设计一个算法：统计一棵二叉树中所有叶结点的数目及非叶结点的数目。

区块链毕设网qklbishe.com为您提供问题的解答

（1）采用递归遍历的思想，这是很容易想到的，因为二叉树是递归定义的。当然也可以用栈实现非递归的算法，时间复杂度相同。在数据结构考试中如果未要求使用非递归算法，一般来说通过递归算法解决树的相关问题，因为递归算法更加直观和易于理解（对于人类而言）。

但是在实际开发中用递归可能会发生栈溢出的情况。

（2）使用C语言实现

//计算总结点个数 int nodeNums(BiTree* root) {     if (!root)         return 0;     else         return nodeNums(root->left) + nodeNums(root->right) + 1; } //计算度数为2的结点总数 int twoChildNodes(BiTree* root) {     if (!root)         return 0;     if (root->left && root->right)         return twoChildNodes(root->left) + twoChildNodes(root->right) + 1;     else         return twoChildNodes(root->left) + twoChildNodes(root->right); } //计算度数为1的结点总数 int oneChildNodes(BiTree* root) {     if (!root)         return 0;     bool only_left = root->left && !root->right;     bool only_right = root->right && !root->left;     if (only_left)         return 1 + oneChildNodes(root->left);     else if (only_right)         return 1 + oneChildNodes(root->right);     else         return oneChildNodes(root->left) + oneChildNodes(root->right); } //计算叶子结点个数 int leaves(BiTree* root) {     if (!root)         return 0;     if (!root->left && !root->right)         return 1;     return leaves(root->left) + leaves(root->right); }

（3）算法类似二叉树的遍历，递归实现的本质也是系统帮我们建立了栈结构，而系统栈需要记住每个节点的值，所以空间复杂度仍为O(N)。

T(N)=2T(N/2)+O(1):，其中 a = 2, b = 2, d = 0;

得到 log(2,2) = 1 > 0，代入Master公式得时间复杂度为O(N)