給你兩棵二叉樹的根節(jié)點 p 和 q ，編寫一個函數(shù)來檢驗這兩棵樹是否相同。

如果兩個樹在結(jié)構(gòu)上相同，并且節(jié)點具有相同的值，則認(rèn)為它們是相同的。
示例 1：

image.png

輸入：p = [1,2,3], q = [1,2,3]

輸出：true
示例 2：

image.png

輸入：p = [1,2], q = [1,null,2]

輸出：false
示例 3：

輸入：p = [1,2,1], q = [1,1,2]

輸出：false

提示：

兩棵樹上的節(jié)點數(shù)目都在范圍 [0, 100] 內(nèi)

-104 <= Node.val <= 104

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

思路1：

使用遍歷的思路，兩棵樹進(jìn)行遍歷，挨個對比葉子節(jié)點。

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 判斷為null的情況，兩個節(jié)點都為null，則返回true，不再遍歷
        if(p == null && q == null){
            return true;
        }
        // 一個節(jié)點為null，則返回false，不再遍歷
        if(p == null){
            return false;
        }

        if(q == null){
            return false;
        }
        // 如果兩個節(jié)點都不為null，且兩個節(jié)點的值不一致，則返回false，不再遍歷
        if(p.val != q.val){
            return false;
        }
        // 遞歸遍歷兩個節(jié)點的左節(jié)點是否一致，若左節(jié)點一致，則再遍歷右節(jié)點
        if(isSameTree(p.left,q.left)){
            return isSameTree(p.right, q.right);
        }
        return false;
    }
}