leetcode 100. Same Tree

100. Same Tree:题目链接

BFS-层次遍历

基本思路：层次遍历两根树 将出队元素进行比较 不同 返回false 注意null结点也要入队(试下题目给出的Example 2:[1,2] [1,nul,2]就知道了)

class Solution {
    // BFS 时间复杂度O(N) N：max(p的结点个数，q的结点个数) 空间复杂度O(M) m:两个队列的大小
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q != null) {
            return false;
        }
        if (p != null && q == null){
            return false;
        }
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();
        q1.offer(p);
        q2.offer(q);
        while (!q1.isEmpty() && !q2.isEmpty()) {
            TreeNode front1 = q1.poll();
            TreeNode front2 = q2.poll();
            if (front1 == null && front2 == null) { // null结点也要入队 比如[1,2] [1,null,2]的情况
                continue;
            }
            // 如果front1空 front2不空 false  
            // front1不空 front2空 false
            // front1.val != front2.val fasle
            if (front1 == null || front2 == null || front1.val != front2.val) {
                return false;
            }
            q1.offer(front1.left); 
            q1.offer(front1.right);
            q2.offer(front2.left);
            q2.offer(front2.right);
        }
        if (q1.size() != 0 || q2.size() != 0){ // 如果最后两个队列中还有队列还有元素 false 
            return false;
        }
        return true;
    }
}

DFS-递归

class Solution {
    
    // 递归宏观语义：返回二叉树p和q是否一样
	// DFS 时间复杂度O(N) N:max(p的结点个数，q的结点个数) 空间复杂度O(N) 递归栈的大小 
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q != null) { // p空 q不空 false
            return false;
        }
        if (p != null && q == null) { // p不空 q空 false
            return false;
        }
        if (p == null && q == null) { // p空 q空 true
            return true;
        }
        if (p.val != q.val) { // 两个结点val不同 false
            return false;
        }
        // 如果p的左子树和q的左子树相同 p的右子树和q的右子树相同 true 否则 false
        return isSameTree(p.left,q.left) && isSameTree(p.right, q.right); 
    }
}