# C++实现LeetCode(100.判断相同树)

## [LeetCode] 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.

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 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 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 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 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;
}
};```

Github 同步地址：

https://github.com/grandyang/leetcode/issues/100

Binary Tree Preorder Traversal

Binary Tree Inorder Traversal

Binary Tree Postorder Traversal

Binary Tree Level Order Traversal

https://leetcode.com/problems/same-tree/

https://leetcode.com/problems/same-tree/discuss/32684/My-non-recursive-method

https://leetcode.com/problems/same-tree/discuss/32687/Five-line-Java-solution-with-recursion