【Leetcode -100.相同的树 -104.二叉树的深度】

YoungMLet

发布于 2024-03-01 10:12:47

820

发布于 2024-03-01 10:12:47

文章被收录于专栏：C++/Linux

Leetcode -100.相同的树

题目：给你两棵二叉树的根节点 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] 内

10^4 <= Node.val <= 10^4

思路：思路是递归，把问题化成子问题是，先判断根，再判断左子树，最后判断右子树，结束条件为一个空另外一个不为空，或者两个指针的值不相同；

		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);
		}

Leetcode -104.二叉树的最大深度

题目：给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明 : 叶子节点是指没有子节点的节点。

示例：给定二叉树[3, 9, 20, null, null, 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;
		}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-06-19，如有侵权请联系 cloudcommunity@tencent.com 删除

leetcode