【题目】
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 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){
//同时到达叶子节点,终止
if(p == NULL && q == NULL){
return true;
}
//不同时到达叶子节点,剪枝
if(p == NULL || q == NULL){
return false;
}
if(p->val == q->val){
bool left = isSameTree(p->left,q->left);
bool right = isSameTree(p->right,q->right);
return left && right;
}
else{
return false;
}
}
};
【迭代】
/*********************************
* 日期：2013-12-08
* 作者：SJF0115
* 题目: 100.Same Tree
* 来源：http://oj.leetcode.com/problems/same-tree/
* 结果：AC
* 来源：LeetCode
* 总结：
**********************************/
/**
* 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){
stack<TreeNode *> stack;
stack.push(p);
stack.push(q);
//迭代
while(!stack.empty()){
//获取节点
q = stack.top();
stack.pop();
p = stack.top();
stack.pop();
//终止,q,p都没有左右节点
if(p == NULL && q == NULL){
continue;
}
//剪枝,有且只有一个没有左右节点,
if(p == NULL || q == NULL){
return false;
}
//剪枝,节点值不一样
if(p->val != q->val){
return false;
}
//遍历左右子节点
stack.push(p->left);
stack.push(q->left);
stack.push(p->right);
stack.push(q->right);
}
return true;
}
};
【测试】
/*********************************
* 日期：2013-12-08
* 作者：SJF0115
* 题目: 100.Same Tree
* 来源：http://oj.leetcode.com/problems/same-tree/
* 结果：AC
* 来源：LeetCode
* 总结：
**********************************/
#include <iostream>
#include <malloc.h>
#include <queue>
#include <stdio.h>
using namespace std;
typedef struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}TreeNode,*BiTree;
//按先序序列创建二叉树
int CreateBiTree(BiTree &T){
int data;
//按先序次序输入二叉树中结点的值，‘-1’表示空树
scanf("%d",&data);
if(data == -1){
T = NULL;
}
else{
T = (BiTree)malloc(sizeof(TreeNode));
//生成根结点
T->val = data;
//构造左子树
CreateBiTree(T->left);
//构造右子树
CreateBiTree(T->right);
}
return 0;
}
bool isSameTree(TreeNode *p, TreeNode *q){
//同时到达叶子节点,终止
if(p == NULL && q == NULL){
return true;
}
//不同时到达叶子节点,剪枝
if(p == NULL || q == NULL){
return false;
}
if(p->val == q->val){
bool left = isSameTree(p->left,q->left);
bool right = isSameTree(p->right,q->right);
return left && right;
}
else{
return false;
}
}
int main() {
int i,n;
BiTree root1,root2= NULL;
CreateBiTree(root1);
CreateBiTree(root2);
printf("%d\n",isSameTree(root1,root2));
return 0;
}
