C++实现判断相同树的功能
本篇内容主要讲解“C++实现判断相同树的功能”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“C++实现判断相同树的功能”吧!
判断相同树
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
判断两棵树是否相同和之前的判断两棵树是否对称都是一样的原理，利用深度优先搜索 DFS 来递归。代码如下：
解法一：
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); }};这道题还有非递归的解法，因为二叉树的四种遍历(层序，先序，中序，后序)均有各自的迭代和递归的写法，这里我们先来看先序的迭代写法，相当于同时遍历两个数，然后每个节点都进行比较，可参见之间那道 Binary Tree Preorder Traversal，参见代码如下：
解法二：
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; }};也可以使用中序遍历的迭代写法，对应之前那道 Binary Tree Inorder Traversal，参见代码如下：
解法三：
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; }};对于后序遍历的迭代写法，貌似无法只是用一个栈来做，因为每次取出栈顶元素后不立马移除，这样使用一个栈的话两棵树结点的位置关系就会错乱，分别使用各自的栈就好了，对应之前那道 Binary Tree Postorder Traversal，参见代码如下：
解法四：
class Solution {public: bool isSameTree(TreeNode* p, TreeNode* q) { stack<TreeNode*> st1, st2; TreeNode *head1, *head2; 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(); head1 = p; head2 = q; p = nullptr; q = nullptr; } else { p = p->right; q = q->right; } } return true; }};对于层序遍历的迭代写法，其实跟先序遍历的迭代写法非常的类似，只不过把栈换成了队列，对应之前那道 Binary Tree Level Order Traversal，参见代码如下：
解法五：
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
到此，相信大家对“C++实现判断相同树的功能”有了更深的了解，不妨来实际操作一番吧！这里是编程网网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
