100. 相同的树

题目描述

输入两棵二叉树的根节点 p 和 q。二叉树按层序写成数组，空位置用 null 表示，例如 [3,9,20,null,null,15,7]。

如果两棵树形状完全一致，并且每个对应位置上的节点值也相等，就认为它们相同，返回 true；否则返回 false。

示例 1

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

示例 2

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

解释：p 的 2 是左孩子，q 的 2 是右孩子，形状不同。

示例 3

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

解释：形状相同，但左右孩子的值对调了。

数据范围

两棵树的节点数都在 [0, 100] 范围内。
-10^4 <= Node.val <= 10^4

解题思路：深度优先搜索（递归）

同步递归：同时走两棵树的对应位置。两个都为空，相同；只有一个为空，结构不同；值不同，不同；否则两棵左子树相同且两棵右子树相同时才相同。

为什么正确

isSameTree(p, q) 为真，当且仅当以 p、q 为根的两棵子树完全相同。

复杂度分析

时间 O(min(m, n))，最坏访问较小那棵树的全部节点；空间 O(min(h1, h2)) 的递归栈。

易错点

只比较中序遍历或层序值序列不够，结构不同的树可能序列相同；判断顺序必须先处理“两个都空”，再处理“只有一个空”，最后再访问 val。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def isSameTree(self, p, q):
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) {
            return true;
        }
        if (!p || !q) {
            return 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
	}
	if p.Val != q.Val {
		return false
	}
	return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

var isSameTree = function(p, q) {
    if (!p && !q) {
        return true;
    }
    if (!p || !q) {
        return false;
    }
    if (p.val !== q.val) {
        return false;
    }
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

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;
    }
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

载入编辑器，自己跑一遍 →

其他解法

递归 DFS 代码最短，空间取决于树高；BFS 用队列按层成对比较，空间取决于树宽，适合想避免递归的场景。

解法 2：广度优先搜索时间 O(min(m,n))，空间 O(min(m,n))

用队列成对地存放两棵树在同一位置的节点。每次取出一对：都为空就跳过；只有一个为空或值不同就返回 false；否则把左孩子对和右孩子对依次入队。队列耗尽仍未发现不同，就是相同的树。

不依赖递归，树很深时不会栈溢出，而且按层比较，差异在上层时能更早发现。代码比递归长，队列在树很宽时会占用较多空间。

from collections import deque

class Solution:
    def isSameTree(self, p, q):
        queue = deque([(p, q)])
        while queue:
            a, b = queue.popleft()
            if not a and not b:
                continue
            if not a or not b or a.val != b.val:
                return False
            queue.append((a.left, b.left))
            queue.append((a.right, b.right))
        return True

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // LinkedList 允许存入 null
        Queue<TreeNode> qu = new LinkedList<>();
        qu.offer(p);
        qu.offer(q);
        while (!qu.isEmpty()) {
            TreeNode a = qu.poll(), b = qu.poll();
            if (a == null && b == null) continue;
            if (a == null || b == null || a.val != b.val) return false;
            qu.offer(a.left);
            qu.offer(b.left);
            qu.offer(a.right);
            qu.offer(b.right);
        }
        return true;
    }
}

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue<pair<TreeNode*, TreeNode*>> qu;
        qu.push({p, q});
        while (!qu.empty()) {
            auto [a, b] = qu.front();
            qu.pop();
            if (!a && !b) continue;
            if (!a || !b || a->val != b->val) return false;
            qu.push({a->left, b->left});
            qu.push({a->right, b->right});
        }
        return true;
    }
};

func isSameTree(p *TreeNode, q *TreeNode) bool {
	queue := [][2]*TreeNode{{p, q}}
	for len(queue) > 0 {
		a, b := queue[0][0], queue[0][1]
		queue = queue[1:]
		if a == nil && b == nil {
			continue
		}
		if a == nil || b == nil || a.Val != b.Val {
			return false
		}
		queue = append(queue, [2]*TreeNode{a.Left, b.Left}, [2]*TreeNode{a.Right, b.Right})
	}
	return true
}

var isSameTree = function(p, q) {
    const queue = [[p, q]];
    let head = 0;
    while (head < queue.length) {
        const [a, b] = queue[head++];
        if (!a && !b) continue;
        if (!a || !b || a.val !== b.val) return false;
        queue.push([a.left, b.left], [a.right, b.right]);
    }
    return true;
};

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    const queue: [TreeNode | null, TreeNode | null][] = [[p, q]];
    let head = 0;
    while (head < queue.length) {
        const [a, b] = queue[head++];
        if (!a && !b) continue;
        if (!a || !b || a.val !== b.val) return false;
        queue.push([a.left, b.left], [a.right, b.right]);
    }
    return true;
}

二叉树专题的其他题目

查看二叉树全部题目 →