承德建设厅网站,hexo用wordpress,望野朗读,网站模板 免费文章目录 相同的树我的思路网上思路队列序列化方法 总结 相同的树 给你两棵二叉树的根节点 p 和 q #xff0c;编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同#xff0c;并且节点具有相同的值#xff0c;则认为它们是相同的。 图一#xff1a;
图二… 文章目录 相同的树我的思路网上思路队列序列化方法 总结 相同的树 给你两棵二叉树的根节点 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
}讲解 初始化队列 创建一个队列将两棵树的根节点 p 和 q 成对放入队列。循环遍历 当队列不为空时进行以下操作 2.1. 取出节点对 从队列中取出一对节点 node1 和 node2。 2.2. 检查是否都为 null 如果 node1 和 node2 都是 null继续下一对节点的比较。 2.3. 检查是否有一个为 null 如果只有一个节点是 null或两个节点的值不同返回 false。 2.4. 入队左右子节点 如果两个节点都存在将它们的左右子节点成对放入队列。返回结果 如果队列处理完毕且没有发现不同返回 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。 总结
序列化的方法看起来挺不错的
