LeetCode算法题目：Same Tree(两种方法解决)

题目：

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.

---

分析：

采用先根遍历对两个二叉树进行遍历，比较其值是否相等。

---

代码：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isSameTree(TreeNode *p, TreeNode *q) { if (p == NULL && q == NULL) return true; else if (p == NULL || q == NULL) return false; return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right); } }; class Solution { public: bool isSameTree(TreeNode *p, TreeNode *q) { if(!isSameNode(p, q)) return false; if(!p && !q) return true; queue<TreeNode*> lqueue; queue<TreeNode*> rqueue; lqueue.push(p); rqueue.push(q); while(!lqueue.empty() && !rqueue.empty()) { TreeNode* lfront = lqueue.front(); TreeNode* rfront = rqueue.front(); lqueue.pop(); rqueue.pop(); if(!isSameNode(lfront->left, rfront->left)) return false; if(lfront->left && rfront->left) { lqueue.push(lfront->left); rqueue.push(rfront->left); } if(!isSameNode(lfront->right, rfront->right)) return false; if(lfront->right && rfront->right) { lqueue.push(lfront->right); rqueue.push(rfront->right); } } return true; } bool isSameNode(TreeNode* p, TreeNode *q) { if(!p && !q) return true; if((p && !q) || (!p && q) || (p->val != q->val)) return false; return true; } };