本篇博客手撕几道经典的二叉树OJ题，它们都很好地体现了二叉树中蕴含的递归思想
题目均已插入超链接，点击即可跳转~
1. 单值二叉树
（1）题目描述
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。
（2）题目分析
如果是空树，则return true，否则要比较左右子树各个结点的值与根节点的值是否相同
思想：递归思想——一棵树可以拆成根+左右子树，左右子树又可以拆成根+左右子树
（3）代码实现
bool isUnivalTree(struct TreeNode* root)
{if(root==NULL){return true;//如果是空树，返回真}int standard=root->val;//记录一下根结点的值作为标准，与左子树和右子树的各节点进行比较if((root->left&&root->left->val!=standard) || (root->right&&root->right->val!=standard)){return false;//两个子节点中有一个不符合就返回false}return isUnivalTree(root->left)&&isUnivalTree(root->right);//确定左右子树都是单值二叉树
}
2.相同的树
（1）题目描述
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
（2）题目分析
思想：递归思想，拆成子问题
根和根比，左子树和左子树比，右子树和右子树比（对于整棵树及其任何子树都可以这么操作）
（3）代码实现
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 isSameTree(p->left, q->left)&&isSameTree(p->right, q->right); return false;
}
变形：对称二叉树，读者可自行尝试。思路提示：根和根比，左子树和右子树比，右子树和左子树比
3.二叉树的前序遍历
（1）题目描述
给你二叉树的根节点 root ，返回它节点值的前序遍历。
注意：前序遍历结果要存到一个数组当中
（2）题目分析
- 关于returnSize：表示数组空间的大小，leetcode要求返回数组的大小，因此把returnSize的地址作为参数放到了函数接口处，函数执行过程中需要获得数组的大小，存入returnSize当中
- 操作步骤：
第一步：确定二叉树结点的个数，进而确定要开辟多大的数组
第二步：对二叉树进行前序遍历，把遍历的结果放到预先开好的数组当中
（3）代码实现
//返回一个数组，里面内容是前序遍历的结果，同时要返回数组的元素个数returnSize//前序遍历
int* prevOrder(struct TreeNode*root,int* a,int* pi)
{if(root==NULL)return NULL;a[*pi] = root->val;(*pi)++;prevOrder(root->left,a,pi);//遍历左子树prevOrder(root->right,a,pi);//遍历右子树return a;
}
//遍历树，确定节点个数，进而确定数组要开多大
int treeSize(struct TreeNode* root)
{if(root==NULL)//空结点，返回0return 0;if(root->left==NULL && root->right==NULL)//说明是叶子节点，返回1return 1;return treeSize(root->left)+treeSize(root->right)+1;//返回左子树结点数+右子树结点数+1
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{*returnSize = treeSize(root);//确定数组要建多大int* a = (int*)malloc(sizeof(int)*(*returnSize));int i = 0;a = prevOrder(root,a,&i);return a;
}
细节：每遍历到一个值放入数组之后，数组下标要+1，那就需要一个下标i来记录，每放入一个值，i就++。因此需要给前序遍历函数传i的地址，保证多次递归调用的时候都会对同一个i进行++操作，此处需要读者理解函数形参和实参的关系（形参是实参的一份临时拷贝），如果不传i的地址，那么前序遍历函数调用的时候，函数内部对i进行++操作不会影响实参的大小
