一、前言
前面我们学习了树与二叉树的相关知识，了解了它的一些基本的相关操作。那么今天我们就来练习一下二叉树的一些相关的OJ题。
此篇博客仅记录博主自己学习的一些有关二叉树的基础OJ题，分享自己的做题过程和想法，如有错误，还请各位指出，这样能帮助我进步，谢谢。
废话少说，我们直接开始吧。
二、单值二叉树
练习链接：单值二叉树
题目描述：如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时，才返回 true；否则返回 false。如下图：（图一是单值二叉树，图二不是）
思路：遍历这棵树，如果每个结点n都和它的孩子节点相等，那么n的孩子也跟n的父亲相等。那么这个二叉树就是一个单值二叉树。
解题代码：
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 ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。如下图：
思路：遍历二叉树，根节点都为空，返回true。一个为空，另一个不为空，返回false。如果都不为空，但是值不相等，返回false。然后递归判断p的左子树和q的左子树是否相等，p的右子树和q的右子树是否相等。
解题代码：
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); }
四、对称二叉树
练习链接：对称二叉树
题目描述：给你一个二叉树的根节点 root ， 检查它是否轴对称。如下图：
true false
思路：两节点都为空返回，即二叉树遍历完毕，返回true；两节点其中一个为空另一个不为空返回false；两节点值不同返回false。
当上面三种情况都不符合时，就进行单层递归：当两节点值相等且有孩子的时候，就需要考虑再次调用函数，来判断一个的左孩子是否与另一个的右孩子相等，一个的右孩子是否与另一个的左孩子相等。
解题代码：
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); }
五、另一颗树的子树
练习链接：另一棵树的子树
题目描述：给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
如下图：第一个是false，第二个是true
思路：每个节点都可以认为是一个子树的根。将原树中所有子树都找出来跟subRoot比较一下，就可以了。我们可以遍历去找它的子树。
解题代码：
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); }
六、判断一棵树是不是平衡二叉树
题目描述：输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
思路：一棵二叉树是平衡二叉树，当且仅当其所有子树也都是平衡二叉树，因此可以使用递归的方式判断二叉树是不是平衡二叉树。
对于当前遍历到的节点，首先计算左右子树的深度，如果左右子树的高度差是否不超过 1，再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。
解题代码：
int BinaryTreeDepth(struct TreeNode* root) { if(root == NULL) return 0; int leftDepth = BinaryTreeDepth(root->left); int rightDepth = BinaryTreeDepth(root->right); return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1; } bool isBalanced(struct TreeNode* root) { if(root == NULL) return true; return (abs(BinaryTreeDepth(root->left)-BinaryTreeDepth(root->right)) <= 1) && isBalanced(root->right) && isBalanced(root->left); }
七、结尾
以上就是今天的全部内容了。写完了上面的四个题。又对二叉树的递归思想有更深的理解了呢。
