0%

[Leetcode]100. Same Tree(C++)

题目描述

题目链接:100. Same Tree

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

例子

例子 1

Input: [1,2,3], [1,2,3]
Output: true

例子 2

Input: [1,2], [1,null,2]
Output: false

例子 3

Input: [1,2,1], [1,1,2]
Output: false

解题思路

用递归方法求解即可,一共有以下四种情况:

  • pq 均为空树,返回 true
  • pq 只有一棵为空树,返回 false
  • pq 值不同,返回 false
  • 其余情况对pq的左右子树分别递归调用 isSameTree()

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) return true;
if ((!p && q) || (p && !q)) return false;
if (p->val != q->val) return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(h) — 考虑递归深度

GitHub 代码同步地址: 100.SameTree.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions