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.
思路一：前序递归的思想。时间复杂度O(n),空间复杂度O(logN)
1 /** 2 * Definition for binary tree 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 16 return (p->val == q->val) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right); 17 } 18 };
思路二：层次遍历的思想。时间复杂度O(n), 空间复杂度O(logN)
1 /** 2 * Definition for binary tree 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 queue<TreeNode *> s; 14 s.push(p); 15 s.push(q); 16 17 while (!s.empty()) { 18 p = s.front(); 19 s.pop(); 20 q = s.front(); 21 s.pop(); 22 if (!p && !q) continue; 23 if (!p || !q) return false; 24 if (p->val != q->val) return false; 25 26 s.push(p->left); 27 s.push(q->left); 28 s.push(p->right); 29 s.push(q->right); 30 } 31 32 return true; 33 } 34 };
原文：http://www.cnblogs.com/vincently/p/4232467.html