【二叉树魔法：链式结构与递归的纠缠】(上)：https://developer.aliyun.com/article/1425242
4.二叉树的节点个数以及高度
// 二叉树节点个数 int BinaryTreeSize(BTNode* root); // 二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root); // 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k); // 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
4.1二叉树节点个数：int BinaryTreeSize(BTNode* root);
求二叉树节点的个数我们最容易想到的就是遍历二叉树，然后遇到一个不为NULL的节点就加，但是我们本章主要是使用递归的思想，所有都采用递归的思想去解题。
// 二叉树节点个数 int BinaryTreeSize(BTNode* root) { int size = 0; if (root == NULL) return 0; else size++; BinaryTreeSize(root->left); BinaryTreeSize(root->right); }
我们首先看看上面的写法有什么错误，很明显，上面犯了一个很严重的错误，返回局部变量的值，我们知道，函数内创建的局部变量在函数释放时候，其空间会被销毁，那么上面的size就会得到一个随机值。
// 二叉树节点个数 int BinaryTreeSize(BTNode* root) { static int size = 0;//静态变量，生命周期边长 if (root == NULL) return 0; else size++; BinaryTreeSize(root->left); BinaryTreeSize(root->right); return size; }
再看看上面的代码，我们将size用static修饰，那么此时size就会存放在静态区，此时size生命周期就会变长，但是在函数内部我们有一个给size初始化为0的语句，这样会不会在每次函数调用的时候都会初始化为0呢？不会，局部的静态变量初始化只会被执行一次。我们调试发现，当再次进入函数时，给size初始化为0的语句直接被跳过了。
运行结果：
我们可以看到结果求出来了，也确实是正确的，但是我们可以发现，静态变量的size生命周期是和程序的生命周期相同的，如果我们后面再次调用函数，size会从上一次的基础上加上去，比如我们再调用一次函数，结果是：
所以我们上面的函数是一次性的，只能使用一次，不方便，不过也有方法解决，我们此时就不用静态变量了，我们将size设置为全局变量，然后在每次调用的时候，手动将size的值赋值为0，但是这样不够优雅，下面我们来介绍一下递归方法。
// 二叉树节点个数 int BinaryTreeSize(BTNode* root) { if (root == NULL) { return 0; } return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1; }
递归图
这样结果就出来啦！！！
4.2二叉树叶子节点个数：int BinaryTreeLeafSize(BTNode* root)
// 二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 1; BinaryTreeSize(root->left) + BinaryTreeSize(root->right); }
递归图：
4.3二叉树第k层节点个数：int BinaryTreeLevelKSize(BTNode* root, int k)
// 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k) { assert(k > 0); if (root == NULL) return 0; if (k == 1) return 1; return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1); }
递归图
4.4二叉树查找值为x的节点：BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
我们首先拿到这个题目，就可以确定我们是从根节点开始查找，然后再左子树，右子树查找，很明显的前序遍历，因此我们可以按照前序遍历的思路查找该值。、
// 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) return NULL; if (root->data == x) return root; BinaryTreeFind(root->left, x); BinaryTreeFind(root->right, x); }
我们看看上面的代码有问题嘛？很明显画个递归图就可以观察到问题。
【二叉树魔法：链式结构与递归的纠缠】(下)：https://developer.aliyun.com/article/1425248
