题目描述
给定两个二叉树,编写一个函数来检验它们是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例:
输入: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] 输出: true
思路
1.一个树相同的条件是根节点,左子树和右子树的完全相同。
2.可以递归的处理两个树的结点,若中途出现以下情况返回false:
- 有一棵树遍历到了NULL,但另一棵树不是NULL
- 两棵树当前结点数值不相等
3.若两者的当前结点都为NULL,说明当前两棵树是相同的,返回true即可。
Java代码实现
public boolean isSameTree(TreeNode p, TreeNode q) { if(p == null && q == null) return true; if((p == null && q != null) || (p != null && q == null)) return false; if(p.val != q.val) return false; return isSameTree(p.left,q.left) && isSameTree(p.right,q.right); }