一、单值二叉树
题目链接
题目描述
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。
思路分析
递归解决：先比较根节点和两个子节点的val，如果不相等就返回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); }
二、相同的树
题目链接
题目描述
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
思路分析
递归解决：比较两棵树根节点的val是否相同，在递归比较左右子树节点的val是否相同。
代码实现
//思路：检查节点的值或者节点的数量是否相同，如果不同直接返回false，然后递归检查左右子树是否相同 bool isSameTree(struct TreeNode* p, struct TreeNode* q){ if(p == NULL && q == NULL) return true; if(p == NULL || q == NULL) //当两棵树中只有一棵树的节点为空时，节点数量不相同时，直接返回false return false; //检查节点和值是否相同 if(p->val != q->val) return false; //检查左右子树是否相同 return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); }
三、对称二叉树
题目链接
题目描述
给你一个二叉树的根节点 root ， 检查它是否轴对称。
思路分析
这道题是上面那道题的一个简单变形，二者在实现思路上大致一样，只是细节上有所不同而已。
由于对称结构是最左边和最右边的节点相同，所以我们需要对 检查两棵子树是否对称 的代码中递归的参数进行调整：
return isSameTree(p->left, q->right) && isSameTree(p->right, q->left);
代码实现
//检查两棵子树是否对称 bool isSameTree(struct TreeNode* p, struct TreeNode* q){ if(p == NULL && q == NULL) return true; if(p == NULL || q == NULL) //当两棵树中只有一棵树的节点为空时，节点数量不相同时，直接返回false return false; //检查节点和值是否相同 if(p->val != q->val) return false; //检查左右子树是否对称 return isSameTree(p->left, q->right) && isSameTree(p->right, q->left); } //思路：将二叉树分为左子树和右子树，检查两棵子树是否对称 bool isSymmetric(struct TreeNode* root){ return isSameTree(root->left, root->right); }
四、二叉树的前序遍历
题目链接
题目描述
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
思路分析
思路分析
二叉树的前序遍历在前面我们已经学过，只是这里有两点需要注意的地方：
1、由于二叉树的节点数数未知的，为了不浪费空间，我们可以先求出二叉树的节点数，然后再开辟对应大小的空间；
2、由于数据是存储在一个数组中，所以我们需要一个变量 i 来控制数组的下标；同时，由于在递归调用过程中对形参的改变不会影响实参，所以这里我们需要传递 i 的地址，通过指针来控制 i 的增长。
代码实现
// 二叉树节点个数 int BinaryTreeSize(struct TreeNode* root) { if (root == NULL) return 0; //左子树节点个数+右子树节点个数+根节点 return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1; } // 二叉树前序遍历 void BinaryTreePrevOrder(struct TreeNode* root, int* ret, int* pi) { if (root == NULL) { return; } //先访问根，再访问左子树，最后访问右子树 ret[*pi] = root->val; (*pi)++; BinaryTreePrevOrder(root->left, ret, pi); BinaryTreePrevOrder(root->right, ret, pi); } //思路：求出二叉树的节点个数，然后malloc等长的数组来存储节点值，最后通过前序遍历将节点值放入数组中 int* preorderTraversal(struct TreeNode* root, int* returnSize){ //求二叉树节点个数 int n = BinaryTreeSize(root); int* ret = (int*)malloc(sizeof(struct TreeNode)*n); //前序遍历 int i = 0; BinaryTreePrevOrder(root, ret, &i); *returnSize = i; return ret; }
五、二叉树的中序遍历
题目链接
题目描述
给定一个二叉树的根节点 root ，返回它的 中序 遍历* 。
思路分析
前序遍历和中序遍历基本上是一样的，只是访问顺序改变而已。
代码实现
// 二叉树节点个数 int BinaryTreeSize(struct TreeNode* root) { if (root == NULL) return 0; //左子树节点个数+右子树节点个数+根节点 return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1; } // 二叉树中序遍历 void BinaryTreeInOrder(struct TreeNode* root, int* ret, int* pi) { if (root == NULL) { return; } //先访问左子树，再访问根，最后访问右子树 BinaryTreeInOrder(root->left, ret, pi); ret[*pi] = root->val; (*pi)++; BinaryTreeInOrder(root->right, ret, pi); } int* inorderTraversal(struct TreeNode* root, int* returnSize){ //求二叉树节点个数 int n = BinaryTreeSize(root); int* ret = (int*)malloc(sizeof(struct TreeNode)*n); //前序遍历 int i = 0; BinaryTreeInOrder(root, ret, &i); *returnSize = i; return ret; }
六、二叉树的后序遍历
题目链接
题目描述
给定一个二叉树的根节点 root ，返回它的 后序 遍历 。
思路分析
后序遍历和前序、中序遍历基本上是一样的，只是访问顺序改变而已。
代码实现
// 二叉树节点个数 int BinaryTreeSize(struct TreeNode* root) { if (root == NULL) return 0; //左子树节点个数+右子树节点个数+根节点 return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1; } // 二叉树前序遍历 void BinaryTreePostOrder(struct TreeNode* root, int* ret, int* pi) { if (root == NULL) { return; } //先访问根，再访问左子树，最后访问右子树 BinaryTreePostOrder(root->left, ret, pi); BinaryTreePostOrder(root->right, ret, pi); ret[*pi] = root->val; (*pi)++; } int* postorderTraversal(struct TreeNode* root, int* returnSize){ //求二叉树节点个数 int n = BinaryTreeSize(root); int* ret = (int*)malloc(sizeof(struct TreeNode)*n); //前序遍历 int i = 0; BinaryTreePostOrder(root, ret, &i); *returnSize = i; return ret; }
七、另一棵树的子树
题目链接
题目描述
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
思路分析
由于root 和 subRoot 中可能含有一个或多个值相同的节点，所以我们只能遍历root，取出其中的每一个节点与subRoot进行比较，看是否相同。
代码实现
//思路：检查节点的值或者节点的数量是否相同，如果不同直接返回false，然后递归检查左右子树是否相同 bool isSameTree(struct TreeNode* p, struct TreeNode* q){ if(p == NULL && q == NULL) return true; if(p == NULL || q == NULL) //当两棵树中只有一棵树的节点为空时，节点数量不相同时，直接返回false return false; //检查节点和值是否相同 if(p->val != q->val) return false; //检查左右子树是否相同 return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); } //思路：遍历root，取root的每一棵子树与sunroot比较，如果相同，就返回true 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); }
九、二叉树构建及遍历
题目链接
题目描述
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
示例1
输入：abc##de#g##f### 输出：c b e g d f a
思路分析
这道题就是把二叉树的构建和二叉树的遍历结合到了一起而已，我们分别完全这两个功能即可。
代码实现
#include <stdio.h> #include <stdlib.h> //符号和结构的定义 typedef char BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; //构建二叉树 BTNode* BinaryTreeCreate(BTDataType* a, int* pi) { if (a[*pi] == '#') { (*pi)++; return NULL; } //创建根节点 BTNode* root = (BTNode*)malloc(sizeof(BTNode)); if (root == NULL) { perror("malloc fail"); exit(-1); } root->data = a[*pi]; (*pi)++; //创建左右子树 root->left = BinaryTreeCreate(a, pi); root->right = BinaryTreeCreate(a, pi); return root; } // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root) { if (root == NULL) { return; } //先访问左子树，再访问根，最后访问右子树 BinaryTreeInOrder(root->left); printf("%c ", root->data); BinaryTreeInOrder(root->right); } int main() { char arr[100]; scanf("%s", arr); //构建二叉树 int i = 0; BTNode* root = BinaryTreeCreate(arr, &i); //二叉树的中序遍历 BinaryTreeInOrder(root); return 0; }
