Check if two binary trees are identical. Identical means the two binary trees have the same structure and every identical position has the same value.
1 1
/ \ / \
2 2 and 2 2
/ /
4 4
are identical.
1 1
/ \ / \
2 3 and 2 3
/ \
4 4
are not identical.
LeetCode上的原题，请参见我之前的博客Same Tree。
解法一：
class Solution { public: /** * @aaram a, b, the root of binary trees. * @return true if they are identical, or false. */ bool isIdentical(TreeNode* a, TreeNode* b) { if (!a && !b) return true; if (!a || !b) return false; return a->val == b->val && isIdentical(a->left, b->left) && isIdentical(a->right, b->right); } };
解法二：
class Solution { public: /** * @aaram a, b, the root of binary trees. * @return true if they are identical, or false. */ bool isIdentical(TreeNode* a, TreeNode* b) { stack<TreeNode*> s1, s2; if (a) s1.push(a); if (b) s2.push(b); 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.empty() && s2.empty(); } };
本文转自博客园Grandyang的博客，原文链接：相同二叉树[LintCode] Identical Binary Tree ，如需转载请自行联系原博主。
