四、另一棵树的子树
链接：572. 另一棵树的子树
描述：
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
示例1：
输入：root = [3,4,5,1,2], subRoot = [4,1,2] 输出：true
示例2：
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] 输出：false
提示：
root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-10^4 <= root.val <= 10^4
-10^4 <= subRoot.val <= 10^4
思路：
这道题算是 相同的树 的进阶版，如果没有我们上一题的铺垫，这题会写的很烦。
我们的主体思路是判断 二叉树的每一棵子树是否和 subRoot 相等。
那么给出我们主要决策：
由于 subRoot 一定不为空，所以一旦 root的子树为空，则返回假；
如果 root 的子树 和 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); }
五、翻转二叉树
链接：226. 翻转二叉树
描述：
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例1：
输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]
示例2：
输入：root = [2,1,3] 输出：[2,3,1]
示例3：
输入：root = [] 输出：[]
提示：
树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100
思路：
对于翻转二叉树，就是把一棵树所有的左右子树对调，这里我们可以使用 后序遍历 的思想。
那么我们基本就可以写出我们的思路：
如果节点为空，那么无需翻转，返回 NULL；
否则就先递归左子树，再递归右子树，到底后，开始交换左右子树，最后逐层返回。
六、对称二叉树
链接：101. 对称二叉树
描述：
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例1：
输入：root = [1,2,2,3,4,4,3] 输出：true
示例2：
输入：root = [1,2,2,null,3,null,3] 输出：false
提示：
- 树中节点数目在范围
[1, 1000]内 -100 <= Node.val <= 100
思路1：
一棵树是否轴对称，可以理解为 它的根节点的 某一边子树翻转 后是否和另一边为 相同的树。
比如我们这边翻转左子树：
我们上方 相同的树 和 翻转二叉树 刚刚写过，那么写这种思路就很简单了。
这题我们也给出相应的决策：
如果左右子树都为空，为根节点，那么返回真；
如果左右子树一遍不为空，那么返回假；
如果左右子树都不为空，那么给定 left 和 right 分别记录左右子树。翻转左边，记录右边；
最后返回判断左右子树是否为相同的树。
接下来我们看看代码怎么写：
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; } 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 isSymmetric(struct TreeNode* root) { // 左右子树都为空 if (root->left == NULL && root->right == NULL) { return true; } // 左右子树一边不为空 if (root->left == NULL || root->right == NULL) { return false; } // 左右子树两边都不为空 struct TreeNode* left, *right; if (root->left && root->right) { // 翻转左边 left = invertTree(root->left); right = root->right; } // 和右边子树比较，返回 bool 值 return isSameTree(left, right); }
但是这种方法也是不太好的，因为破坏了原本二叉树的结构，那么还有更好的方法吗？看思路2。
思路2：
一棵树对称就是 它的左右子树呈镜像状态 。说白了就是节点左子树的值等于右子树的值，右子树的值等于左子树的值。
那么我们可以用一个 check 函数来递归检查，并将二叉树的根节点传两份过去：
如果两棵树都为空，返回真；
如果两棵树一棵为空，另一棵不为空，返回假；
如果两棵树都不为空，但是值不相等，返回假；
上面的走完都没有返回，那么就分别递归第一棵树的左子树和第二棵树的右子树；第一棵树的右子树和第二棵树的左子树。
最后返回 check 函数的真值，就能判断出结果。
七、二叉树的前序遍历
描述：
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3] 输出：[1,2,3]
示例 2:
输入：root = [] 输出：[]
示例3：
输入：root = [1] 输出：[1]
示例 4:
输入：root = [1,2] 输出：[1,2]
示例 5：
输入：root = [1,null,2] 输出：[1,2]
提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
思路：
这里的前序遍历和之前的有所不同，题目要求我们将遍历结果存到数组中，将数组返回，且空指针不需要记录。
那么我们可以计算出二叉树的大小，然后 动态开辟一个二叉树大小的数组。
并使用一个下标来记录数组的元素个数，最后 前序遍历二叉树 ，将结果存入数组，返回数组。
相关题目：
相关题目和这道题思路类似，我就不带着大家看了，大家自己下去可以试试。
八、平衡二叉树
链接：110. 平衡二叉树
描述：
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例1：
输入：root = [3,9,20,null,null,15,7] 输出：true
示例2：
输入：root = [1,2,2,3,3,null,null,4,4] 输出：false
示例3：
输入：root = [] 输出：true
提示：
树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104
思路：
所谓 平衡二叉树就是任意节点的子树的高度差都小于等于1。
基于这个理解，那么我们可以将它分成子问题：每个节点的子树的高度差小于等于1。
那么就可以给出思路：
如果节点为空，则是完全二叉树；
否则就求左右两边子树高度；
再判断左右子树的 高度差的绝对值 是否 大于1 ，大于1则一定不是完全二叉树，返回假；
最后分别递归左右子树，判断左右子树是否满足完全二叉树的条件。
求高度的就是我们上篇博客的 计算二叉树的高度 的接口。
完整代码：
int TreeHeight(struct TreeNode* root) { if (root == NULL) { return 0; } int leftHeight = TreeHeight(root->left); int rightHeight = TreeHeight(root->right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } bool isBalanced(struct TreeNode* root) { // 根节点为空，是完全二叉树 if (root == NULL) { return true; } // 求左右两边高度 int leftHeight = TreeHeight(root->left); int rightHeight = TreeHeight(root->right); // 绝对值大于1一定不是完全二叉树 if (abs(leftHeight - rightHeight) > 1) { return false; } return isBalanced(root->left) && isBalanced(root->right); }
