二叉树比较

算法思路

判断两棵二叉树是否完全相同（结构一致且对应节点值相等）。

递归比较当前节点：

• 两节点都为空 → 相同
• 仅一方为空 → 不同
• 值不等 → 不同
• 否则递归比较左子树与左子树、右子树与右子树

时间 O(n)，空间 O(h)（h 为树高，递归栈）。

python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def is_same_tree(p: TreeNode, q: TreeNode) -> bool:
    if not p and not q:
        return True
    if not p or not q:
        return False
    if p.val != q.val:
        return False
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

js

function TreeNode(val=0, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function isSameTree(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);
}

go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func isSameTree(p, 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)
}