前言
在二叉树的学习中，我们学习了递归的思想，但是还需要刷题来真正弄明白这种思想。希望下面的几道经典oj题对你有所帮助。
1. 单值二叉树
OJ链接
深度优先搜索
一棵树的所有节点都有相同的值，当且仅当对于树上的每一条边的两个端点，它们都有相同的值（这样根据传递性，所有节点都有相同的值）。
因此，我们可以对树进行一次深度优先搜索。当搜索到节点 x 时，我们检查 x与 x 的每一个子节点之间的边是否满足要求。例如对于左子节点而言，如果其存在并且值与 x 相同，那么我们继续向下搜索该左子节点；如果值与 x不同，那么我们直接返回 False。
bool isUnivalTree(struct TreeNode* root) { if(root==NULL) { return true; } if(root->left!=NULL&&root->val!=root->left->val) { return false; } if(root->right!=NULL&&root->val!=root->right->val) { return false; } return isUnivalTree(root->left)&&isUnivalTree(root->right); }
2. 检查两颗树是否相同
OJ链接
如果两个二叉树都为空，则两个二叉树相同。如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同。
如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。这是一个递归的过程，因此可以使用深度优先搜索，递归地判断两个二叉树是否相同。
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->left,q->left)&&isSameTree(p->right,q->right); }
3. 对称二叉树
OJ链接
如果一个树的左子树与右子树镜像对称，那么这个树是对称的。
因此，该问题可以转化为：两个树在什么情况下互为镜像？
如果同时满足下面的条件，两个树互为镜像：
它们的两个根结点具有相同的值
每个树的右子树都与另一个树的左子树镜像对称
我们可以实现这样一个递归函数，左子树的右子树与右子树的左子树相同，左子树的左子树与右子树的右子树相同，这样就形成了镜面对称。
bool judge(struct TreeNode* left,struct TreeNode*right) { if(left==NULL&&right==NULL) { return true; } if(left==NULL||right==NULL) { return false; } if(left->val!=right->val) { return false; } return judge(left->left,right->right)&&judge(left->right,right->left); } bool isSymmetric(struct TreeNode* root) { if(root==NULL) { return true; } return judge(root->left,root->right); }
4. 二叉树的前序遍历
OJ链接
其实这道题就是一个简单的前序遍历，只是把打印换成了将数据存入数组
int TreeSize(struct TreeNode* root) { /*if (root == NULL) { return; } size++; TreeSize(root->left); TreeSize(root->right);*/ return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; } void preorder(struct TreeNode* root, int* pi,int *a) { if(root==NULL) { return ; } a[(*pi)++]=root->val; preorder(root->left,pi,a); preorder(root->right,pi,a); } int* preorderTraversal(struct TreeNode* root, int* returnSize) { *returnSize=TreeSize(root); int *a =(int *)malloc(sizeof(int)*(*returnSize)); int i=0; preorder(root,&i,a); return a; }
5. 另一颗树的子树。
OJ链接
这道题目其实和查找二叉树数值为x的那个函数很像，我们只要看每个子树和右边那个树是否相等即可。
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->left,q->left)&&isSameTree(p->right,q->right); } bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) { if(root==NULL) { return false; } if(isSameTree(root,subRoot)) { return true; } return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot); }
6.二叉树的构建及遍历
OJ链接
因为前序遍历的顺序是：根，左子树，右子树。所以我们在读取他来创建二叉树的时候也是这个顺序，我们先创建根，让根与其左子树和右子树相连，而左子树又可以分为左子树的根与其左子树和右子树相连……以此就构建了递归。这里我们只需要注意最后的结束条件，就是出现#，就返回NULL。
typedef struct BinaryTreeNode { char data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; } BTNode; BTNode *CreatTree(char *a,int *pi) { if(a[*pi]=='#') { (*pi)++; return NULL; } BTNode*node=(BTNode*)malloc(sizeof(BTNode)); node->data=a[(*pi)++]; node->left=CreatTree(a, pi); node->right=CreatTree(a, pi); return node; } void Inorder(BTNode*root) { if(root==NULL) { return; } Inorder(root->left); printf("%c ",root->data); Inorder(root->right); } int main() { char a[100]; scanf("%s",a); int i=0; BTNode*root=CreatTree(a,&i); Inorder(root); return 0; }
7.翻转二叉树：
OJ链接
这是一道很经典的二叉树问题。显然，我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root 为根节点的整棵子树的翻转。
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; }
