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:递归解法,如果根节点相同,再递归的看左子树和右子树是否相同
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 // IMPORTANT: Please reset any member data you declared, as14 // the same Solution instance will be reused for each test case.15 if(p && q)16 {17 if(p->val == q->val && isSameTree(p->left, q->left) && 18 isSameTree(p->right, q->right))19 return true;20 else return false;21 }22 else if(p || q)23 return false;24 else return true;25 }26 };
算法2:通过层序遍历,分别用两个队列保存两棵树的层序节点。每次从两个队列中分别取出一个元素,如果他们的值相同,再继续遍历子节点。注意每次取出的两个元素的左子树要么同时非空,要么同时为空,右子树也一样
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 // IMPORTANT: Please reset any member data you declared, as14 // the same Solution instance will be reused for each test case.15 queuepQueue, qQueue;16 if(p)pQueue.push(p);17 if(q)qQueue.push(q);18 while(pQueue.empty() == false && qQueue.empty() == false)19 {20 TreeNode *pp = pQueue.front();21 TreeNode *qq = qQueue.front();22 pQueue.pop(); qQueue.pop();23 if(pp->val == qq->val)24 {25 if(pp->left && qq->left)26 {27 pQueue.push(pp->left);28 qQueue.push(qq->left);29 }30 else if(pp->left || qq->left)31 return false;32 if(pp->right && qq->right)33 {34 pQueue.push(pp->right);35 qQueue.push(qq->right);36 }37 else if(pp->right || qq->right)38 return false;39 }40 else return false;41 }42 if(pQueue.empty() && qQueue.empty())43 return true;44 else return false;45 }46 };
【版权声明】转载请注明出处: