首页 > 代码库 > leetcode - Same Tree

leetcode - Same Tree

题目: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、比较两棵树是否相同,先比较根节点是否相同,再分别比较左子树和右子树是否相同,可以看出这是一个递归的过程,一般树的题目都会涉及递归

 

代码:

 1 #include <stddef.h> 2 /* 3 struct TreeNode 4 { 5     int val; 6     TreeNode *left; 7     TreeNode *right; 8     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 9 };10 */11 class Solution12 {13 public:14     bool isSameTree(TreeNode *p, TreeNode *q)15     {16         //p,q均为空17         if (p == NULL && q == NULL)18         {19             return true;20         }21 22         //p,q不为空时,p,q指向结点的值相同且p,q左右子树均相同,则说明p,q指向的树相同23         if (p != NULL && q != NULL && p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right))24         {25             return true;26         }27 28         return false;29     }30 };
View Code

 

按照惯例,到网上搜寻是否有更好的方法,发现大部分都是采用这种递归的思路,就这样吧