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

[LeetCode] 100. Same Tree 判断相同树 Given two binary trees, write a function to check if they are the same or not.

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

Ouwww.cppcns.comtput: 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;
}
};http://www.cppcns.com```

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

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