繁霜尽是心头血
洒向千峰秋叶丹
目录
二叉树最大的深度
思路
代码展示
单值二叉树
思路
代码展示
相同的树
思路
代码展示
对称二叉树
思路
代码展示
另一颗树的子树
思路
代码展示
二叉树最大的深度
题目链接：二叉树最大的深度
给定一个二叉树
root，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：3示例 2：
输入：root = [1,null,2] 输出：2提示：
- 树中节点的数量在
[0, 10^4]区间内。-100 <= Node.val <= 100
思路
例如 如果我们知道了左子树和右子树的最大深度 l 和 r
那么该二叉树的最大深度即 max(l，r) + 1（左右子树的最大深度加根节点）
我们可以把它看做是后序遍历（左右根），函数递归完再用其返回值做树的高度计算
步骤
<1>确定终止条件：如果根为空节点的话，就返回0，表示高度为0
if(root == NULL) return 0;<2>找出重复的子问题：递归左子树的最大高度，递归右子树的最大高度
int left = maxDepth(root->left); int right = maxDepth(root->right);<3>根据题目进行整改：求出左右子树的最大高度再进行比较，取最大高度在加一
return (left>right?left:right)+1;
代码展示
int maxDepth(struct TreeNode* root) { if(root == NULL) return 0; int left = maxDepth(root->left); int right= maxDepth(root->right); return (left>right?left:right)+1; }时间复杂度为 O(n) ：在递归过程中每个节点都被遍历到
空间复杂度为 O(n) ：此外在递归过程中调用了额外的栈空间，栈的大小取决于二叉树的高度，设二叉树最坏情况下的高度为 n
注意：
public int maxDepth(TreeNode root) { if(root == null) return 0; return 1 + (maxDepth(root.left) > maxDepth(root.right)? maxDepth(root.left):maxDepth(root.right)); }这样写逻辑上是对的，但是会超时，因为多算了几遍 maxDepth( ) ，多递归了，应该用变量存储一下 maxDepth( ) 的值
单值二叉树
题目链接：单值二叉树
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回
true；否则返回false。示例 1：
输入：[1,1,1,1,1,null,1] 输出：true示例 2：
输入：[2,2,2,5,2] 输出：false提示：
- 给定树的节点数范围是
[1, 100]。- 每个节点的值都是整数，范围为
[0, 99]。
思路
因为单值二叉树每个节点都具有相同的值，那么我们只要比较左右子树节点的值是否与根节点相同。如果我们从正面来判断一个树是否为单值二叉树很难，所以我们可以考虑反面。例如 左子树为空或者节点的值不等于根节点的值即返回 false 我们每次判断都返回反面结果，最后不满足条件的必然是 true
步骤
<1>确定终止条件：如果节点为空，说明比较到了尽头，返回 true
if(root == NULL) return true;<2>判断单值二叉树的条件：判断树的左右子树是否为空以及节点的值是否等于根的值
if(root->left && root->left->val != root->val) return false; if(root->right && root->right->val != root->val) return false;<3>找出重复的子问题：递归左右子树判断是否满足相等的条件
return isUnivalTree(root->left) && isUnivalTree(root->right);
代码展示
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); }时间复杂度O(n)：其中 n 是二叉树的节点个数。我们遍历二叉树的每个节点至多一次。
空间复杂度O(n)：即为深度优先搜索中需要使用的栈空间。
相同的树
题目链接：相同的树
给你两棵二叉树的根节点
p和q，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3] 输出：true示例 2：
输入：p = [1,2,1], q = [1,1,2] 输出：false提示：
- 两棵树上的节点数目都在范围
[0, 100]内-10^4 <= Node.val <= 10^4
思路
判断两棵二叉树是否相同，可以通过递归对二叉树各个节点进行比较，以判断两棵树是否相同。
步骤
<1>确定终止条件
如果两个节点都为空，说明比较到了尽头，返回 true 如果一个节点为空，另一个节点不为空，两节点不同，返回 false if(p == NULL && q == NULL) return true; if(p == NULL || q == NULL) return false;<2>判断相同二叉树的条件：如果 p 和 q 都不为空，判断根结点值是否相同，相同则继续判断两颗树的左右子树值都相同，返回 true，否则返回 false
if(p->val != q->val) return false;<3>找出重复的子问题：递归判断两颗树的左右子树判断是否相同
return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
代码展示
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， 检查它是否轴对称。示例 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
思路
对称二叉树如图所示，要判断一个二叉树是否为对称二叉树，实际上就是要判断根节点的左右两个子树是否镜像对称
那么两个树在什么情况下互为镜像？
两个树的根结点具有相同的值 每个树的右子树都与另一个树的左子树镜像对称
我们可以借助上一题的思路，我们把这个树的左右子树拆解成两个树进行判断
例如 我们用 root1 代表左子树的根，root2 代表右子树的根，然后递归先判断树的节点是否对称再判断 root1 的左子树和 root2 的右子树 值 是否相同
<1>确定终止条件
（1）如果两个节点都为空，说明比较到了尽头，返回 true
（2）如果一个节点为空，另一个节点不为空，则树不对称，返回 false
if(root1 == NULL && root2 ==NULL) return true; if(root1 == NULL || root2 == NULL) return false;<2>判断对称二叉树的条件：判断 root1 的左子树和 root2 的右子树 值 是否相同
if(root1->val != root2->val) return false;<3>找出重复的子问题：递归判断两颗树的左右子树的镜像是否对称以及值是否相等
return _isSymmetric(root1->left,root2->right)&&_isSymmetric(root1->right,root2->left);
代码展示
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) { return _isSymmetric(root->left,root->right); }假设树上一共 n 个节点。
时间复杂度：这里遍历了这棵树，渐进时间复杂度为 O(n)。
空间复杂度：这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 n，故渐进空间复杂度为 O(n)。
另一颗树的子树
题目链接：另一颗树的子树
给你两棵二叉树
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
思路
如何判断一个树是另一个树的子树呢？就和我们找子数组一样（找相同）
<1>我们可以定义两个指针（指针p 指向root的比较节点，指针q 指向subRoot的根）
<2>先从 root 的左树开始，位置于root当前节点的指针p 与 在subRoot根节点的指针q 共同遍历进行比较，若节点与节点值相同则代表 subRoot 为子树，否则再递归右树，仍然没有则不是子树
找相同的代码我们可以借助之前（相同的树的代码）
判断subRoot是否是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); }<1>确定终止条件：树的节点为空说明树不存在或者递归到了尽头，直接返回 false
if (root == NULL) return false;<2>判断子树的条件：判断 root 的枝干和 subRoot 的是否相同，相同返回 true
bool rootBool = isSameTree(root,subRoot);<3>找出重复的子问题：递归root的左右子树判断是否有枝干与subRoot一致
return rootBool || isSubtree(root->left, subRoot) || isSubtree(root->right, 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; bool rootBool = isSameTree(root,subRoot); return rootBool || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot); }
