学习记录：js算法（四十七）：相同的树

相同的树

给你两棵二叉树的根节点 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

我的思路
递归
网上思路

我的思路

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

讲解
基本情况：

• 如果 p 和 q 都是 null，返回 true。
• 如果只有一个是 null，返回 false。
• 如果两个节点的值不同，返回 false。
  递归：
• 递归调用 isSameTree 来比较左子树和右子树。
• 只有当左子树和右子树都相同时，整个树才相同。

网上思路

队列

 var isSameTree = function (p, q) {const queue = [[p, q]]; // 初始化队列，存储节点对while (queue.length > 0) {const [node1, node2] = queue.shift(); // 从队列中取出一对节点// 如果两个节点都是 null，继续比较下一个if (node1 === null && node2 === null) {continue;}// 如果只有一个节点是 null，或者值不同，返回 falseif (node1 === null || node2 === null || node1.val !== node2.val) {return false;}// 将左右子节点加入队列queue.push([node1.left, node2.left]);queue.push([node1.right, node2.right]);}return true; // 如果遍历完成都没有发现不同，返回 true
}

讲解

1. 初始化队列 创建一个队列，将两棵树的根节点 p 和 q 成对放入队列。
2. 循环遍历 当队列不为空时，进行以下操作：
   2.1. 取出节点对 从队列中取出一对节点 node1 和 node2。
   2.2. 检查是否都为 null 如果 node1 和 node2 都是 null，继续下一对节点的比较。
   2.3. 检查是否有一个为 null 如果只有一个节点是 null，或两个节点的值不同，返回 false。
   2.4. 入队左右子节点 如果两个节点都存在，将它们的左右子节点成对放入队列。
3. 返回结果 如果队列处理完毕且没有发现不同，返回 true。

序列化方法

var isSameTree = function (p, q) {function serialize(root) {if (root === null) {return 'null,'; // 用 'null' 表示空节点}// 先序遍历，节点值与左右子树的序列化结果return root.val + ',' + serialize(root.left) + serialize(root.right);}// 序列化两棵树并比较return serialize(p) === serialize(q);
};

讲解
序列化函数 serialize(root)：

• 编写一个辅助函数，将二叉树转换为字符串。可以使用前序遍历（pre-order traversal）来实现。
• 如果当前节点是 null，返回字符串 ‘null,’。
• 否则，返回当前节点的值与左右子树的序列化结果，使用逗号 , 分隔。
  主函数 isSameTree(p, q)：
• 调用 serialize 函数对两棵树进行序列化。
• 比较两个序列化后的字符串，若相同则返回 true，否则返回 false。

总结

序列化的方法看起来挺不错的