版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~
- 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.
-
题目大意：给定两棵二叉树，写一个函数来判断它们是否相等。两棵二叉树相等的条件是两棵二叉树的结构相同并且结点值相等。
-
思路：可以用递归也可以把递归改成非递归（所有的递归都可以改写成非递归的形式）。
不管递归还是非递归，判断条件都是一样的，（1）首先判断当前结点是否为NULL，如果都为NULL，显然是相等的，（2）如果不是两棵树的当前结点都为NULL，其中有一个为NULL，那么两棵树必不相等，（3）如果两棵树的两个结点的值不相等，那么两棵树必不相等。条件判断完后，说明当前结点相等且不为NULL。接下来就再判断当前结点的左右子树，在递归方法中，用递归手段去判断；在非递归方法中，将当前结点的左右孩子结点入队，在去循环判断。由此可见，递归、非递归，思想是一样的。
-
代码：
-
数据结构定义：
// Definition for binary tree
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) {
// 先判断当前结点的情况，看是否相等
// 两个结点都是NULL，返回true
if(p==NULL && q==NULL) return true;
// 两个结点其中有一个是NULL，返回false
else if(p==NULL || q==NULL) return false;
// 两个结点的值不相等，返回false
else if(p->val != q->val) return false;
//两棵二叉树，当前结点相等，递归判断左右子树
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};
- 方法二
class Solution {
public:
// 非递归思想实现，用两个栈进行层序遍历，遍历过程中对结点进行判断
bool isSameTree(TreeNode *p, TreeNode *q) {
queue<TreeNode *> q1, q2;
TreeNode *tmp1, *tmp2;
q1.push(p), q2.push(q);
while(!q1.empty() && !q2.empty()){
tmp1 = q1.front();
tmp2 = q2.front();
q1.pop(); q2.pop();
// 判断两棵树的当前结点是否都NULL
if(tmp1==NULL && tmp2==NULL) continue;
// 非都NULL，其中有一个NULL，必不相等
else if(tmp1==NULL || tmp2==NULL) return false;
// 两棵树的两个结点的值不相等，必不相等
else if(tmp1->val != tmp2->val) return false;
// 前三个判断条件都没走，说明q1不为NULL
q1.push(tmp1->left);
q1.push(tmp1->right);
// 前三个判断条件都没走，说明q2不为NULL
q2.push(tmp2->left);
q2.push(tmp2->right);
}//while
// 结束循环后，队列有至少一个非NULL，说明两棵二叉树结构不一样，必不相等
if(!q1.empty() || !q2.empty()) return false;
return true;
}
};
- 以上。
版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~
网友评论