100. 相同的树

Posted on In Views: Disqus:
LeetCode刷题系列。

描述

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1:

1
2
3
4
5
6
7
输入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true

示例 2:

1
2
3
4
5
6
7
输入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

输出: false

示例 3:

1
2
3
4
5
6
7
输入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

输出: false

来源：力扣（LeetCode）
链接：100. Same Tree

解题思路

在101. 对称二叉树这道题的解题经验之上，很容易一遍过，也是难得的一遍过，显然是刚才101题的解法还在脑海里面火热。

本题主要采用递归解法，对于给定的两个二叉树，根据题意，其相同的条件如下：

  • 根节点的值相同
  • 左右子树也分别相同

根据这样的条件，再判断根节点为空的两种情况，不难写出递归的代码，具体代码如下：

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 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 && !q) return true;
    if(!p || !q) return false;
    
    return (p->val == q->val) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}