【基础篇 - Day 14】 2023-02-26 - 100.相同的树 （03. 树 ）

[threedayAAAAA]

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

 

示例 1：

输入：p = [1,2,3], q = [1,2,3] 输出：true 示例 2：

输入：p = [1,2], q = [1,null,2] 输出：false 示例 3：

输入：p = [1,2,1], q = [1,1,2] 输出：false  

提示：

两棵树上的节点数目都在范围 [0, 100] 内 -104 <= Node.val <= 104

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/same-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[threedayAAAAA]

思路一

思路

层序遍历

代码

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    if(q?.val !== p?.val){
        return false
    }
    let AFloor = [p]
    let BFloor = [q]
    while(AFloor.length || BFloor.length){
        const newAFloor = getNextFloor(AFloor)
        const newBFloor = getNextFloor(BFloor)
        if(!validateFloor(newAFloor, newBFloor)){
            return false
        }
        AFloor = newAFloor.filter(Boolean)
        BFloor = newBFloor.filter(Boolean)
    }
    return true
};

function validateFloor(floorA: TreeNode[], floorB: TreeNode[]){
    if(floorA.length !== floorB.length) return false
    return floorA.every((item, index) => item?.val === floorB[index]?.val)
}

function getNextFloor(floor: TreeNode[]){
    const nextFloor = [] 
    floor.forEach(item => {
        nextFloor.push(item?.left ?? null)
        nextFloor.push(item?.right ?? null)
    })
    return nextFloor
}

时空复杂度

• 时间复杂度：O(N)
• 空间复杂度: O(N)

思路二

思路

深序遍历

代码

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    if(p === null || q === null){
        return q?.val === p?.val
    }
    return q .val === p.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};

时空复杂度

• 时间复杂度：O(N)
• 空间复杂度： O(N)

[MiumMi]

思路

递归进行深度遍历即可

代码

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    if (p === null || q == null) {
        return p?.val ===q?.val;
    }
    return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

---

分析

1. 时间复杂度：O(n)
2. 空间复杂度：O(n) ?存疑

[yunliuyan]

思路

• DFS算法
• 当p,q都为null，返回true；当p,q其中一个为null，返回false，当p，q的值不相等，返回false
• 返回左右节点的递归

代码

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    if(!p && !q) {
        return true;
    }
    if (!p || !q) {
        return false;
    }
    if (p.val !== q.val) {
        return false;
    }
    const isEqualLeft = isSameTree(p.left, q.left);
    const isEqualRight = isSameTree(p.right, q.right);

    return isEqualLeft && isEqualRight;
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度： O(n)