题目描述:(链接)
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.
解题思路:
迭代版
1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 bool isSameTree(TreeNode* p, TreeNode* q) { 13 stack<TreeNode *> cache; 14 cache.push(p); 15 cache.push(q); 16 17 while (!cache.empty()) { 18 p = cache.top(); cache.pop(); 19 q = cache.top(); cache.pop(); 20 if (!p && !q) continue; 21 if (!p || !q) return false; 22 if (p->val != q->val) return false; 23 24 cache.push(p->left); 25 cache.push(q->left); 26 cache.push(p->right); 27 cache.push(q->right); 28 } 29 30 return true; 31 } 32 };
递归版：
1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 bool isSameTree(TreeNode* p, TreeNode* q) { 13 if (!p && !q) return true; 14 if (!p || !q) return false; 15 if (p->val != q->val) return false; 16 17 return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); 18 } 19 };
原文：http://www.cnblogs.com/skycore/p/5011102.html