用 Javascript 判断二叉树是否相同的方法

在计算机科学中，二叉树是一种重要的数据结构。在很多实际应用场景中，我们常常需要判断两个二叉树是否相同。本文将介绍使用Javascript来实现判断二叉树是否相同的方法。

我们需要明确二叉树相同的定义。两个二叉树相同当且仅当它们的结构相同，并且对应节点的值也相同。也就是说，两个二叉树的根节点值相等，且它们的左子树和右子树也分别相同。

下面是一个使用递归方法来判断二叉树是否相同的Javascript代码示例：

// 定义二叉树节点结构体
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

// 判断二叉树是否相同的函数
function isSameTree(p, 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);
}

在上述代码中，isSameTree函数接受两个二叉树的根节点p和q作为参数。首先判断两个节点是否都为空，如果是，则返回true，表示两个子树相同。如果其中一个为空，另一个不为空，则返回false。然后比较两个节点的值，如果不相等，则返回false。最后，递归地判断它们的左子树和右子树是否相同。

使用这种递归方法的时间复杂度为$O(n)$，其中$n$是二叉树中节点的数量，因为需要遍历每个节点进行比较。空间复杂度取决于递归调用的栈空间，最坏情况下为$O(n)$，平均情况下为$O(log n)$。

在实际应用中，我们可以通过创建二叉树节点并调用isSameTree函数来判断两个二叉树是否相同。例如：

// 创建两个二叉树
let tree1 = new TreeNode(1);
tree1.left = new TreeNode(2);
tree1.right = new TreeNode(3);

let tree2 = new TreeNode(1);
tree2.left = new TreeNode(2);
tree2.right = new TreeNode(3);

console.log(isSameTree(tree1, tree2)); 

通过上述方法，我们可以方便地使用Javascript判断两个二叉树是否相同，这在处理二叉树相关的算法和数据结构问题时非常有用。