Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
Example 1:
Input:
1 1
/ \ / \
2 3 2 3
Output: true
Example 2:
Input:
1 1
/ \
2 2
Output: false
题目
判断两棵二叉树是否相等
思路
二叉树题目一般都需要递归，这也是由于二叉树本身就是递归结构。
递归三步走：
- 终止条件（也可理解为最小样本情况）
- 自己调用自己
- 处理返回值
回到题目本身：
- 终止条件：当两个节点其中一个为空，或值不相等时，返回false;当两个节点都为空时，返回true；当两个节点不为空且值相等时，继续往下找；
- 所以递归也就形成了，就是判断两棵树的左右孩子是否相同，自己调自己，分别传入左右孩子；
- 返回值，那就是（左孩子是否相等&右孩子是否相等）
所以有代码如下：
代码
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
if (p.val != q.val) {
return false;
}
boolean sameOrNotLeft = isSameTree(p.left, q.left);
boolean sameOrNotright = isSameTree(p.right, q.right);
return sameOrNotLeft && sameOrNotright;
}
