Leetcode第100题——相同的树

48 阅读 0 评论 32 点赞

我是靠谱客的博主风趣凉面，最近开发中收集的这篇文章主要介绍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⁴ <= Node.val <= 10⁴

解题思路
题目要求很明确，判断二叉树每个节点的值是否相等，如果当前节点的值为空，而另一个不为空可直接判为两树不相等，若当前节点两树均为空则视为两节点值相等，我们从根结点出发，依次递归判断当前节点的左右子节点是否相等，直至所有对应节点都相等或都为空，则证明两数相等，反之不相等。

代码-C语言：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *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 isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
    else
        return false;
}