1. 单值二叉树
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。
链接：https://leetcode-cn.com/problems/univalued-binary-tree/
输入：[1,1,1,1,1,null,1]
输出：true
输入：[2,2,2,5,2]
输出：false
思路：
如果是一棵空树，它也是单值二叉树；如果树不为空，先判断它左孩子的值和根是否相同，相同则是单值二叉树，反则不是；在判断它的右孩子的值和根是否相同，相同则是单值二叉树，反则不是；但是我们不知道树的深度是多少，我们就要进行递归去判断它得到左子树和右子树，必须满足左右子树都是单值二叉树，整个树才是单值二叉树；
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);
2. 对称二叉树
给你一个二叉树的根节点
root， 检查它是否轴对称。链接：https://leetcode-cn.com/problems/symmetric-tree/submissions/
思路：
1.如果是一棵空树，他一定是对称的二叉树；
2.如果不是空树，判断这棵树有没有左右子树，如果没有，则是对称的二叉树，反之则不是；
3.如果左右子树只存在一个，就不是对称的二叉树；
4.接下来去判断左子树的左值是否和右子树的右值相等，左子树的右值和右子树的左值是否相等；
bool _isSymmetric(struct TreeNode* root1,struct TreeNode* root2) { //左右子树为空 if(root1 == NULL && root2 == NULL) { return true; } //左右子树有一个为空 if(root1==NULL ||root2==NULL) { return false; } //左右值不相等 if(root1->val != root2->val) { return false; } //递归左子树的左和右子树的右 和 递归左子树的右和右子树的左 return _isSymmetric(root1->left,root2->right) && _isSymmetric(root1->right,root2->left); } bool isSymmetric(struct TreeNode* root){ if(root==NULL) { return true; } return _isSymmetric(root->left,root->right); }
3. 相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
链接：https://leetcode-cn.com/problems/same-tree/submissions/
思路：
1.如果两棵树都是空树，肯定是相同的树；
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 false; } return isSameTree(p->left,q->left) && isSameTree(p->right,q->right); }
4. 二叉树的前序遍历
链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/submissions/
前序遍历相对来说理解其原来，实现不是很困难；这道题要注意几个地方，输出结果是以数组的形式输出的，我们要给多大的数组呢？ 测试用例多样化，我们可以给到一个二叉树的结点给树函数，让其求出结点个数，然后去开辟空间；这样就不会造成浪费；给到的函数中有这样一个参数int* returnSize，这是输出型参数，就是数组的元素个数；也就是我们算出来的二叉树的结点个数；
后面的中序遍历和后续遍历同样如此；
int TreeSize(struct TreeNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; } void _preorderTraversal(struct TreeNode* root, int* a,int* pi) { if(root == NULL) { return; } a[(*pi)++] = root->val;//根 _preorderTraversal(root->left, a, pi);//左 _preorderTraversal(root->right, a, pi);//右 } int* preorderTraversal(struct TreeNode* root, int* returnSize){ int size=TreeSize(root); int* a = malloc(sizeof(int)*size); int i = 0; _preorderTraversal(root, a, &i); *returnSize = size; return a; }
5. 二叉树的中序遍历
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
int TreeSize(struct TreeNode* root) { return root == NULL ? 0 : TreeSize(root->left)+TreeSize(root->right) + 1; } void _inorderTraversal(struct TreeNode* root,int* a,int* pi) { if(root == NULL) { return; } _inorderTraversal(root->left, a, pi); //左 a[(*pi)++] = root->val; //根 _inorderTraversal(root->right, a, pi);//右 } int* inorderTraversal(struct TreeNode* root, int* returnSize){ int size = TreeSize(root); int* a = malloc(sizeof(int) * size); int i = 0; _inorderTraversal(root, a, &i); *returnSize = size; return a; }
