【题目】
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;
}
分享到:
相关推荐
* [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...
leetcode 答案leetcode-java leetcode.com 的 Java 答案 ================索引================ com.leetcode.array Search a ...com.leetcode.list ...com.leetcode.string ...com.leetcode.tree ...Same Tree
https://leetcode.com/problems/same-tree/ Same Tree 101 https://leetcode.com/problems/symmetric-tree/ Symmetric Tree 102 https://leetcode.com/problems/binary-tree-level-order-traversal/ Binary Tree ...
leetcode 2 和 c Leetcode_questions 目前拥有: 简单的: 1.二和(c) 7.反转整数(c) 9.回文数(c) ...100.Same Tree(c++) 101.对称树(c++) 104.二叉树的最大深度(c++) 108.将排序数组转换为二叉搜索树
与大家分享我学习算法的...数组/链表:树相关:AVLTree 平衡二叉搜索树BinaryHeap 二叉堆(优先队列)Num2TreeSum 数组树的和MaxDepth4Tree (leetcode 104)ValidBinarySearchTree (leetcode 98)SameTree (leetcode 100)...
leetcode-js Leecode 经典题目 JavaScript TypeScript 题解...100.相同的树 (Same Tree) 104.二叉树的最大深度 (Maximum Depth of Binary Tree) 118.杨辉三角 (Pascal's Triangle) 119.杨辉三角 II (Pascal's Triangle)
删除过于简单题目(例:100题:Same Tree) 删除题意不同,代码基本相同题目(例:136 & 389,保留一个) 所有题目尽量保证客观公正,只是按大概率删除不常考题目,很多题目面经出现过, 但出现次数属于个位数或者...
Leetcode的ac是什么意思 LeetCodeInJava List #98 Validate Binary Search Tree #100 Same Tree #104 Maximum Depth of Binary Tree #122 Best Time to Buy and Sell Stock II #136 Single Number #150 Evaluate ...
[100_same-tree.cpp] [1001_sorted-merge-lcci.cpp] [101_对称树.cpp] [102_binary-tree-level-order-traversal.cpp] [103_binary-tree-zigzag-level-order-traversal.cpp] [104_maximum-depth-of-binary-tree.cpp] ...
同一棵树:#[./LeetCode/100_Same Tree.cpp] 序列化和反序列化二叉树:# 将根数与叶数相加:# 二叉搜索树 最低共同祖先:1); 2) 红黑树 AVL树 展开树 段树RMQ:范围最小查询 DFS:由,由 (单一来源) (所有对) ...
##NO.100 Same Tree 这道题是关于二叉树的题,非常基础的题,递归思路。这道题主要就是熟悉二叉树的相关操作,这里给出了一个前序输入二叉树的函数。 ##NO.112 Path Sum 这道题是关于二叉树的题,递归思路,也就是...
leetcode 答案 leetcode 08/18 Unique Paths 应该是简单的数学排列组合问题,提炼一下其实就一句话:...Same Tree 这种简单的二叉树遍历,丝毫没有难度啊。。 Insertion Sort List 在这里遇到前所未遇的惨败——提交了
sameTree: find_content_children: LeetCode 算法题 时间复杂度和空间复杂度权衡,时间复杂度的提升是以空间复杂度为代价的 仔细观察,LeetCode 上对每一次代码的提交的 执行时间 && 消耗内存 效率 = 算法效率 + ...
leetcode分发糖果 Leetcode C++ Solution Don't try to understand it, feel ...21-合并两个有序链表:merge-two-sorted-lists 83-删除排序链表中的重复元素:...100-相同的二叉树:same-tree 101-对称二叉树:symmetric-
Same Tree Symmetric Tree Balanced Binary Tree Flatten Binary Tree to Linked List Populating Next Right Pointers in Each Node II 二叉树的构建 Construct Binary Tree from Preorder and Inorder Traversal ...