叶子节点的个数
叶子节点就是数的枝叶，最末端节点，没有子节点的节点，结合上图来说就是4，9，2节点
递归函数我们要清楚自己的要求，当遇到满足条件时响应对应的变化，也要确定好归的条件。
叶子节点没有子节点，即这个节点的left和right都为空，和上边求节点个数类似，遍历整棵树，满足条件再++。
代码如下
int BinaryTreeLeafSize(BTNode* root) { if (root == NULL) { return 0; } if (root->right && root->left == NULL) { return 1; } return BinaryTreeLeafSize(root->right) + BinaryTreeLeafSize(root->left); }
当遇到叶子节点就没必要继续向下找了，有些节点只有一个节点，还是不满足左右都为NULL，但是还是会遍历他的为空的节点，所以root==NULL为空，还是要返回。
第k层节点个数
思路：这个时候就要考验条件筛选能力了，要找第K层节点个数，第一个思路就是直接递归找到第k层后，判断是否为空，如果不为空就使返回值++，在上层遍历时如果没有到第K层就遇到了空就返回。
也可以这样，找到第k-1层，判断该层的子节点数。怎么计算都可以，两种方法差别不大
第一种写法代码如下。
// 二叉树第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); }
先断言一下层数是否错误。思路和前边介绍大致相同，只不过转化为了代码逻辑。一定要注意我们要实现什么功能，从而对症下药。
查找某值并返回
查找值为x的节点
上边的题都是遍历后返回总和，返回的数在每次递归中变化，现在要返回的是一个节点，如果查找到节点后返回，然后再递归的话，每个函数有不同的返回值，这种题目还是很难搞的，还是需要思路清晰，明确自己想要什么，不然就会可能会改变我们最终想要的结果。
画递归展开图是最好的排查错误的方法。
通过控制递归的返回值，接受判断，如果已经找到了就不再递归下去，直接将结果归回起始的函数，就可以完成任务。
代码如下
// 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) { return NULL; } if (root->data == x) { return root; } BTNode* ret = NULL; ret=BinaryTreeFind(root->left, x); if (ret != NULL) { return ret; } ret = BinaryTreeFind(root->right, x); if (ret != NULL) { return ret; } return NULL; }
返回值要在每个函数里判断一下，当然如果根节点的data就是x的话就直接返回该节点，如果不是就递归到左节点，如果左节点找到后会返回到调用的地方，然后会判断查找的结果是否为NULL，为空再继续调用右边的。
这道题有必要画一下递归展开图
还是以上边的图为例哈
假设查找节点值为9的节点
序号步骤十分清晰，这种递归十分巧妙，检查返回值，使所找节点直线返回。
判断树的结点的值相关问题
单值二叉树
Leetcode:单值二叉树
判断二叉树节点的所有值是否相同。
遍历全部节点，如果有一个树节点的左右子节点的储存的值与根节点不同，那么就返回false，遇到空节点就返回true，因为并不矛盾单值二叉树。
代码如下
bool isUnivalTree(struct TreeNode* root){ if(root==NULL) { return true; } if(root->left&&root->left->val!=root->val) { return false; } if(root->right&&root->right->val!=root->val) { return false; } return isUnivalTree(root->left)&&isUnivalTree(root->right); }
遍历所有节点，除非遇到空返回，遇到节点值与根节点不同的就返回false，最后返回左树和右树返回值的并且，只有两个皆为真，返回true，如果其中一个为假，就返回false，还有一个值得提出的就是，如果左树就找到false，就不会访问右树了，因为&&的前一个判断条件如果为假，就直接返回假，右树不会再遍历。
相同的树
Leetcode:相同的树
给定两个树，判断其保存的值是否相等。
先看根节点，再判断两树的左节点，右节点，如果有两个节点不相等就返回false，如果两个树都为空返回true，两个节点不相等返回false，相等就继续向下遍历。
思路清晰明了了
代码如下
bool isSameTree(struct TreeNode* p, struct TreeNode* q){ if(p==NULL&&q==NULL) { return true; } if(p==NULL||q==NULL) { return false; } if(p->val!=q->val) { return false; } return isSameTree(p->right,q->right)&&isSameTree(p->left,q->left); }
&&判断返回结果，上边已经介绍过了他的功能和强大之处，这里就不再赘述了。
数的结构的问题
这种类型的题目和前边的有一点不同，前边的不是做出判断就是获取节点的值，或者是统计数目，这种类型的题目是明确树的结构，想要做什么，实现什么操作，将树更改为题目要求的样子。
翻转二叉树
Leetcode:翻转二叉树
每个节点的左右节点都要反转，从根节点开始，把所有非空子节点的左右节点都换位，保存其左右节点，然后互换，两个都为空，换一换也无所谓，其中一个节点不为空，另一个节点为空，交换。
代码如下
struct TreeNode* invertTree(struct TreeNode* root){ if(root==NULL) { return NULL; } struct TreeNode*left=invertTree(root->left); struct TreeNode*right=invertTree(root->right); root->left=right; root->right=left; return root; }
对称二叉树
Leetcode:对称二叉树
检查一个树是否为对称二叉树。
是bu是感觉无从下手啊
这道题其实用前边的函数就可以实现。
相同的树以及翻转二叉树
将根节点的左子树翻转，再与右子树判断是否为相同的树。
代码如下
struct TreeNode* invertTree(struct TreeNode* root){ if(root==NULL) { return NULL; } struct TreeNode*left=invertTree(root->left); struct TreeNode*right=invertTree(root->right); //都找到了叶子节点 // struct TreeNode*tmp=left; // left=right; // right=tmp; root->left=right; root->right=left; return root; } bool isSameTree(struct TreeNode* p, struct TreeNode* q){ if(p==NULL&&q==NULL) { return true; } if(p==NULL||q==NULL) { return false; } if(p->val!=q->val) { return false; } return isSameTree(p->right,q->right)&&isSameTree(p->left,q->left); } bool isSymmetric(struct TreeNode* root){ struct TreeNode*head=invertTree(root->right); return isSameTree(head,root->left); }
是不是柳暗花明，恍然大悟！
利用二叉树相关的问题对递归的讲解到这里就结束啦，最重要的还是判断结束条件以及具体想实现的内容，利用逻辑将其用代码表达出来。
本文到此结束，如果有什么错误的地方欢迎指针。
