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
題目
判斷兩棵二叉樹是否相等
思路
二叉樹題目一般都需要遞歸，這也是由于二叉樹本身就是遞歸結(jié)構(gòu)罩句。
遞歸三步走：
- 終止條件（也可理解為最小樣本情況）
- 自己調(diào)用自己
- 處理返回值
回到題目本身：
- 終止條件：當(dāng)兩個節(jié)點(diǎn)其中一個為空，或值不相等時姑廉，返回false;當(dāng)兩個節(jié)點(diǎn)都為空時，返回true茧泪；當(dāng)兩個節(jié)點(diǎn)不為空且值相等時器腋，繼續(xù)往下找伏钠；
- 所以遞歸也就形成了，就是判斷兩棵樹的左右孩子是否相同蚂蕴，自己調(diào)自己盼忌，分別傳入左右孩子；
- 返回值掂墓，那就是（左孩子是否相等&右孩子是否相等）
所以有代碼如下：
代碼
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;
}
