leetcode-100. Same Tree · Tree + DFS + Queue

题面

对比两棵二叉树是否相同，返回结果。

思路

1. 递归解决DFS

首先判断根节点，如果都空，返回true；

如果一空一不空，返回false；

如果都不空，判断两节点值是否相同，若不同，返回false，若相同，递归左子树、右子树

源码

 /**

  * 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 == nullptr && q == nullptr)

             return true;

         else if(p == nullptr || q == nullptr)

             return false;

         else

         {

             if(p->val == q->val)

                 return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);

             else

                 return false;

         }

     }

 };

2. 层序遍历解决: 队列

1. 首先判断根节点，如果都空，返回true；

2. 如果一空一不空，返回false；

3. 如果都不空，新建队列，两节点入队。如果队列不空，出队两个元素，如果都为空，继续continue（而不是像判断头节点那样返回true），如果一空一不空，返回false;

4. 如果都不空，判断该值是否相等，若不相等，返回false; 若相等，那么分别将当前节点左孩子（2个）、右孩子（2个）入队，循环。

即：这种方法是为了在过程中返回false,最后遍历完毕，返回true.

源码

 class Solution {

 public:

     bool isSameTree(TreeNode* p, TreeNode* q) {

         if(p == nullptr && q == nullptr)

             return true;

         else if(p == nullptr || q == nullptr)

             return false;

         queue<TreeNode*> tmp;

         tmp.push(p); tmp.push(q);

         while(!tmp.empty())

         {

             TreeNode *pp, *qq;

             pp = tmp.front(); tmp.pop();

             qq = tmp.front(); tmp.pop();

             if(pp == nullptr && qq == nullptr)

                 continue;

             else if(pp == nullptr || qq == nullptr)

                 return false;

             if(pp->val != qq->val)

                 return false;

             else

             {

                 tmp.push(pp->left); tmp.push(qq->left);

                 tmp.push(pp->right); tmp.push(qq->right);

             }

         }

         return true;

     }

 };

巴特西

leetcode-100. Same Tree · Tree + DFS + Queue

最新文章

热门文章