【算法专栏】对称的二叉树
本系列是《剑指offer》或leetcode的JavaScript版本。 每期1-2个算法，也有可能是一个类别。 文章包括题目、思路以及代码。 如果您对本期有不同或者更好的见解，请后台留言，喜欢请点个好看，谢谢阅读。
题目1-对称的二叉树
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
思路
二叉树的右子树是二叉树左子树的镜像二叉树。
镜像二叉树：两颗二叉树根结点相同，但他们的左右两个子节点交换了位置。
如图，1为对称二叉树，2、3都不是。
- 两个根结点相等
- 左子树的右节点和右子树的左节点相同。
- 右子树的左节点和左子树的右节点相同。
递归所有节点满足以上条件即二叉树对称。
代码
function isSymmetrical(pRoot) { return isSymmetricalTree(pRoot, pRoot); }
function isSymmetricalTree(node1, node2) { if (!node1 && !node2) { return true; } if (!node1 || !node2) { return false; } if (node1.val != node2.val) { return false; } return isSymmetricalTree(node1.left, node2.right) && isSymmetricalTree(node1.right, node2.left); }题目2-序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树
思路
- 若一颗二叉树是不完全的，我们至少需要两个遍历才能将它重建（像题目重建二叉树一样）
- 但是这种方式仍然有一定的局限性，比如二叉树中不能出现重复节点。
- 如果二叉树是一颗完全二叉树，我们只需要知道前序遍历即可将它重建。
- 因此在序列化时二叉树时，可以将空节点使用特殊符号存储起来，这样就可以模拟一棵完全二叉树的前序遍历
- 在重建二叉树时，当遇到特殊符号当空节点进行处理
代码
function Serialize(pRoot, arr = []) { if (!pRoot) { arr.push('#'); } else { arr.push(pRoot.val); Serialize(pRoot.left, arr) Serialize(pRoot.right, arr) } return arr.join(','); }
function Deserialize(s) { if (!s) { return null; } return deserialize(s.split(',')); }
function deserialize(arr) { let node = null; const current = arr.shift(); if (current !== '#') { node = { val: current } node.left = deserialize(arr); node.right = deserialize(arr); } return node; }本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-05-20，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读