题目:给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例 1:
输入:p = [1, 2, 3], q = [1, 2, 3] 输出:true
示例 2:
输入:p = [1, 2], q = [1, null, 2] 输出:false
示例 3:
输入:p = [1, 2, 1], q = [1, 1, 2] 输出:false
提示: 两棵树上的节点数目都在范围[0, 100] 内
思路:思路是递归,把问题化成子问题是,先判断根,再判断左子树,最后判断右子树,结束条件为一个空另外一个不为空,或者两个指针的值不相同;
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
//两个指针为空,返回true到上一层递归
if (p == NULL && q == NULL)
return true;
//前面已经判断过两个指针都不为空,
//所以到这里如果有一个指针为空,另外一个肯定不为空,即不相同,返回false到上一层递归
if (p == NULL || q == NULL)
return false;
//比较值如果不相同,返回false到上一层递归
if (p->val != q->val)
return false;
//递归
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
题目:给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明 : 叶子节点是指没有子节点的节点。
示例: 给定二叉树[3, 9, 20, null, null, 15, 7],
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
思路:思路是用递归,每次递归看作去找左子树和右子树的较大值,如果当前节点返回了一个值,就把自己加上返回上一层;注意这里要记录每次递归的返回值,防止丢失数据后又递归回去找数据;
int maxDepth(struct TreeNode* root)
{
//如果树为空,返回0
if (root == NULL)
return 0;
//记录每次递归的返回值,防止丢失数据后又递归回去找数据
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
//返回左右子树中较大的值加一,因为算上自己的节点
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}