分享程序员开发的那些事...
更新时间：2022-09-13 22:45:01
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
判断两棵树是否相同和之前的判断两棵树是否对称都是一样的原理，利用深度优先搜索DFS来递归。代码如下：
解法一：
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); } };
这道题还有非递归的解法，因为二叉树的四种遍历(层序，先序，中序，后序)均有各自的迭代和递归的写法，这里我们先来看先序的迭代写法，相当于同时遍历两个数，然后每个节点都进行比较，参见代码如下：
解法二：
public: bool isSameTree(TreeNode* p, TreeNode* q) { stack<TreeNode*> s1, s2; if (p) s1.push(p); if (q) s2.push(q); while (!s1.empty() && !s2.empty()) { TreeNode *t1 = s1.top(); s1.pop(); TreeNode *t2 = s2.top(); s2.pop(); if (t1->val != t2->val) return false; if (t1->left) s1.push(t1->left); if (t2->left) s2.push(t2->left); if (s1.size() != s2.size()) return false; if (t1->right) s1.push(t1->right); if (t2->right) s2.push(t2->right); if (s1.size() != s2.size()) return false; } return s1.size() == s2.size(); } };
其他几种遍历顺序的迭代写法应该也能实现，有时间补充完整~
参考资料：
https://leetcode.com/discuss/22197/my-non-recursive-method
本文转自博客园Grandyang的博客，原文链接：[LeetCode] Same Tree 判断相同树
，如需转载请自行联系原博主。