🥉easy

🥉Easy
题解
- 深度优先遍历
- 广度优先遍历
  - Python
  - JavaScript

给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1:

输入:          1        1
          / \       / \
         2   3     2   3
        [1,2,3],   [1,2,3]
输出: true

示例 2:

输入:      1          1
          /           \
         2             2
        [1,2],     [1,null,2]
输出: false

示例 3:

输入:       1         1
          / \       / \
         2   1     1   2
        [1,2,1],   [1,1,2]
输出: false

题解

这道题还是比较容易的，直接递归遍历就行，但树方面练习确实太少了，需要多刷题！！
一般比较容易想到树的深度优先遍历，但广度优先没想到

深度优先遍历

如果两个二叉树都为空，则两个二叉树相同。如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同。

如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。这是一个递归的过程，因此可以使用深度优先搜索，递归地判断两个二叉树是否相同。

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        elif not p or not q:
            return False
        elif p.val != q.val:
            return False
        else:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

JavaScript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if (p === null && q === null){
        return true
    } else if (p === null || q === null){
        return false
    } else if (p.val !== q.val) {
        return false
    } else {
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
    }
};

复杂度分析

时间复杂度：。其中m和n是两个二叉树对应的节点数。对两个二叉树同时进行深度优先搜索，只有当两个二叉树的对应节点都不为空时才会访问到该节点，因此被访问到的节点数不会超过较小的二叉树的节点数
空间复杂度：。其中m和n是两个二叉树对应的节点数。空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数。
广度优先遍历

同样首先判断两个二叉树是否为空，如果两个二叉树都不为空，则从两个二叉树的根节点开始广度优先搜索。

使用两个队列分别存储两个二叉树的节点。初始时将两个二叉树的根节点分别加入两个队列。每次从两个队列各取出一个节点，进行如下比较操作。

比较两个节点的值，如果两个节点的值不相同则两个二叉树一定不同；

如果两个节点的值相同，则判断两个节点的子节点是否为空，如果只有一个节点的左子节点为空，或者只有一个节点的右子节点为空，则两个二叉树的结构不同，因此两个二叉树一定不同；

如果两个节点的子节点的结构相同，则将两个节点的非空子节点分别加入两个队列，子节点加入队列时需要注意顺序，如果左右子节点都不为空，则先加入左子节点，后加入右子节点。

如果搜索结束时两个队列同时为空，则两个二叉树相同。如果只有一个队列为空，则两个二叉树的结构不同，因此两个二叉树不同。

Python

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False

        queue1 = collections.deque([p])
        queue2 = collections.deque([q])

        while queue1 and queue2:
            node1 = queue1.popleft()
            node2 = queue2.popleft()
            if node1.val != node2.val:
                return False
            left1, right1 = node1.left, node1.right
            left2, right2 = node2.left, node2.right
            if (not left1) ^ (not left2):
                return False
            if (not right1) ^ (not right2):
                return False
            if left1:
                queue1.append(left1)
            if right1:
                queue1.append(right1)
            if left2:
                queue2.append(left2)
            if right2:
                queue2.append(right2)

        return not queue1 and not queue2

JavaScript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function (p, q) {
    // 判断到最终节点相同 返回true
    if (p === null && q === null) return true
    // 两个树不是同时遇到最终节点 返回false
    if (p === null || q === null) return false

    let dp1 = [p],
        dp2 = [q]

    while (dp1.length && dp2.length) {
        let node1 = dp1.shift(),
            node2 = dp2.shift()
        if (node1.val !== node2.val) {
            return false
        }
        let left1 = node1.left,
            right1 = node1.right,
            left2 = node2.left,
            right2 = node2.right
        // 异或，均为false或者均为true 结果为false，不然为true
        if ((left1 === null) ^ (left2 === null)) return false
        if ((right1 === null) ^ (right2 === null)) return false
        // 该节点相同，继续推送下一个节点进行比较
        if (left1 !== null) dp1.push(left1)
        if (right1 !== null) dp1.push(right1)
        if (left2 !== null) dp2.push(left2)
        if (right2 !== null) dp2.push(right2)
    }
    // 所有节点比较完成返回true
    return dp1.length === 0 && dp2.length === 0
}

🥉100. 相同的树🌱

🥉Easy

题解

深度优先遍历

Python

JavaScript

复杂度分析

广度优先遍历

Python

JavaScript