## 题目地址

https://leetcode.com/problems/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.

Example 1:

``````Input:     1         1
/ \       / \
2   3     2   3

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

Output: true
``````

Example 2:

``````Input:     1         1
/           \
2             2

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

Output: false
``````

Example 3:

``````Input:     1         1
/ \       / \
2   1     1   2

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

Output: false
``````

## 代码

``````class Solution {
public:
bool isSameTree(TreeNode *p, TreeNode *q) {
if (!p && !q) return true;
if ((p && !q) || (!p && q) || (p->val != q->val)) return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};
``````

``````class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
stack<TreeNode*> st;
st.push(p); st.push(q);
while (!st.empty()) {
p = st.top(); st.pop();
q = st.top(); st.pop();
if (!p && !q) continue;
if ((p && !q) || (!p && q) || (p->val != q->val)) return false;
st.push(p->right); st.push(q->right);
st.push(p->left); st.push(q->left);
}
return true;
}
};
``````

``````class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
stack<TreeNode*> st;
while (p || q || !st.empty()) {
while (p || q) {
if ((p && !q) || (!p && q) || (p->val != q->val)) return false;
st.push(p); st.push(q);
p = p->left; q = q->left;
}
p = st.top(); st.pop();
q = st.top(); st.pop();
p = p->right; q = q->right;
}
return true;
}
};
``````

``````class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
stack<TreeNode*> st1, st2;
while (p || q || !st1.empty() || !st2.empty()) {
while (p || q) {
if ((p && !q) || (!p && q) || (p->val != q->val)) return false;
st1.push(p); st2.push(q);
p = p->left; q = q->left;
}
p = st1.top();
q = st2.top();
if ((!p->right || p->right == head1) && (!q->right || q->right == head2)) {
st1.pop(); st2.pop();
p = nullptr; q = nullptr;
} else {
p = p->right;
q = q->right;
}
}
return true;
}
};
``````

``````class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
queue<TreeNode*> que;
que.push(p); que.push(q);
while (!que.empty()) {
p = que.front(); que.pop();
q = que.front(); que.pop();
if (!p && !q) continue;
if ((p && !q) || (!p && q) || (p->val != q->val)) return false;
que.push(p->right); que.push(q->right);
que.push(p->left); que.push(q->left);
}
return true;
}
};
``````

评论
0 评论