题面
对比两棵二叉树是否相同，返回结果。
思路
1. 递归解决DFS
首先判断根节点，如果都空，返回true；
如果一空一不空，返回false；
如果都不空，判断两节点值是否相同，若不同，返回false，若相同，递归左子树、右子树
源码
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 == nullptr && q == nullptr) 14 return true; 15 else if(p == nullptr || q == nullptr) 16 return false; 17 else 18 { 19 if(p->val == q->val) 20 return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); 21 else 22 return false; 23 } 24 } 25 };
2. 层序遍历解决: 队列
1. 首先判断根节点，如果都空，返回true；
2. 如果一空一不空，返回false；
3. 如果都不空，新建队列，两节点入队。如果队列不空，出队两个元素，如果都为空，继续continue（而不是像判断头节点那样返回true），如果一空一不空，返回false;
4. 如果都不空，判断该值是否相等，若不相等，返回false; 若相等，那么分别将当前节点左孩子（2个）、右孩子（2个）入队，循环。
即：这种方法是为了在过程中返回false,最后遍历完毕，返回true.
源码
1 class Solution { 2 public: 3 bool isSameTree(TreeNode* p, TreeNode* q) { 4 if(p == nullptr && q == nullptr) 5 return true; 6 else if(p == nullptr || q == nullptr) 7 return false; 8 queue<TreeNode*> tmp; 9 tmp.push(p); tmp.push(q); 10 while(!tmp.empty()) 11 { 12 TreeNode *pp, *qq; 13 pp = tmp.front(); tmp.pop(); 14 qq = tmp.front(); tmp.pop(); 15 if(pp == nullptr && qq == nullptr) 16 continue; 17 else if(pp == nullptr || qq == nullptr) 18 return false; 19 20 if(pp->val != qq->val) 21 return false; 22 else 23 { 24 tmp.push(pp->left); tmp.push(qq->left); 25 tmp.push(pp->right); tmp.push(qq->right); 26 } 27 } 28 return true; 29 } 30 };
leetcode-3100. Same Tree · Tree + DFS + Queue
原文：https://www.cnblogs.com/yocichen/p/10902695.html