LeetCode 100. 相同的树

Categories:

题目描述
思路分析
1. 解法一：递归 DFS（推荐）
2. 解法二：迭代 BFS
相似题目

题目描述

✅ 100. 相同的树

思路分析

解法一：递归 DFS（推荐）

核心思路：

两棵树相同的条件：结构完全一致，且对应节点的值相等。

递归终止条件：若两个节点都为空，则相同；若只有一个为空，则不同；若值不相等，则不同。

递归比较左右子树：当前节点满足条件后，继续递归判断左子树与右子树是否分别相同。

复杂度分析：

时间复杂度：O(n)，其中 n 表示两棵树中节点的总数，每个节点最多访问一次。

空间复杂度：O(h)，其中 h 表示树的高度，递归调用栈的深度最大为树的高度；最坏情况下（链式树）退化为 O(n)。

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 两个节点都为空，结构相同
        if (p == null && q == null) {
            return true;
        }
        // 只有一个节点为空，结构不同
        if (p == null || q == null) {
            return false;
        }
        // 节点值不相等，直接返回 false
        if (p.val != q.val) {
            return false;
        }
        // 递归比较左子树和右子树
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

func isSameTree(p *TreeNode, q *TreeNode) bool {
    // 两个节点都为空，结构相同
    if p == nil && q == nil {
        return true
    }
    // 只有一个节点为空，结构不同
    if p == nil || q == nil {
        return false
    }
    // 节点值不相等，直接返回 false
    if p.Val != q.Val {
        return false
    }
    // 递归比较左子树和右子树
    return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

解法二：迭代 BFS

核心思路：

使用队列同时对两棵树进行层序遍历，每次取出对应位置的节点成对比较。

若两个节点都为空则跳过；若只有一个为空或值不相等则返回 false。

将两棵树对应的左右子节点依次入队，直到队列为空则说明两棵树完全相同。

复杂度分析：

时间复杂度：O(n)，其中 n 表示两棵树中节点的总数，每个节点最多入队一次。

空间复杂度：O(n)，其中 n 表示两棵树中节点的总数，队列中最多同时存储 O(n) 个节点。

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 使用队列同时对两棵树进行 BFS
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(p);
        queue.offer(q);

        while (!queue.isEmpty()) {
            TreeNode nodeP = queue.poll();
            TreeNode nodeQ = queue.poll();

            // 两个节点都为空，继续遍历
            if (nodeP == null && nodeQ == null) {
                continue;
            }
            // 只有一个为空，或值不相等，返回 false
            if (nodeP == null || nodeQ == null || nodeP.val != nodeQ.val) {
                return false;
            }

            // 将左右子节点成对入队
            queue.offer(nodeP.left);
            queue.offer(nodeQ.left);
            queue.offer(nodeP.right);
            queue.offer(nodeQ.right);
        }

        return true;
    }
}

func isSameTree(p *TreeNode, q *TreeNode) bool {
    // 使用切片模拟队列，同时对两棵树进行 BFS
    queue := []*TreeNode{p, q}

    for len(queue) > 0 {
        nodeP := queue[0]
        nodeQ := queue[1]
        queue = queue[2:]

        // 两个节点都为空，继续遍历
        if nodeP == nil && nodeQ == nil {
            continue
        }
        // 只有一个为空，或值不相等，返回 false
        if nodeP == nil || nodeQ == nil || nodeP.Val != nodeQ.Val {
            return false
        }

        // 将左右子节点成对入队
        queue = append(queue, nodeP.Left, nodeQ.Left)
        queue = append(queue, nodeP.Right, nodeQ.Right)
    }

    return true
}

相似题目

题目	难度	考察点
101. 对称二叉树	简单	递归、DFS、二叉树对称判断
572. 另一棵树的子树	简单	递归、DFS、二叉树匹配
951. 翻转等价二叉树	中等	递归、DFS、二叉树结构比较
226. 翻转二叉树	简单	递归、DFS、二叉树操作
104. 二叉树的最大深度	简单	递归、DFS/BFS、二叉树遍历
110. 平衡二叉树	简单	递归、DFS、二叉树高度

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/95440840