题目描述
题目链接: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
解题思路
用递归方法求解即可,一共有以下四种情况:
p
、q
均为空树,返回true
p
、q
只有一棵为空树,返回false
p
、q
值不同,返回false
- 其余情况对
p
、q
的左右子树分别递归调用isSameTree()
代码如下:
/**
* 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