共计 7789 个字符，预计需要花费 20 分钟才能阅读完成。
最近有粉丝和我交换面试遇到的算法题。其中有一道题比拟有意思，分享给大家。
ta 说本人面试了一家某大型区块链的公司的前端岗位，被问到了一道算法题。这道题也是一个十分常见的题目了，力扣中也有原题 110. 均衡二叉树，难度为简略。
不过面试官做了一点点小的扩大，难度霎时降级了。咱们来看下面试官做了什么扩大。
题目
题目是《判断一棵树是否为均衡二叉树》，所谓均衡二叉树指的是 二叉树中所有节点的 左右子树的深度之差不超过 1。输出参数是二叉树的根节点 root，输入是一个 bool 值。
代码会被以如下的形式调用：
console.log(isBalance([3, 9, 2, null, null, 5, 5]));
console.log(isBalance([1, 1, 2, 3, 4, null, null, 4, 4]));思路
求解的思路就是围绕着二叉树的定义来进行即可。
对于二叉树中的每一个节点都：
- 别离计算左右子树的高度，如果高度差大于 1，间接返回 false
- 否则持续递归调用左右子节点，如果左右子节点全部都是均衡二叉树，那么返回 true。否则返回 false
能够看出咱们的算法就是 死扣定义。
计算节点深度比拟容易，既能够应用 前序遍历 + 参考扩大 的形式，也可应用 后序遍历 的形式，这里我用的是 前序遍历 + 参数扩大。
对此不相熟的强烈建议看一下这篇文章 简直刷完了力扣所有的树题，我发现了这些货色。。。
于是你能够写出如下的代码。
function getDepth(root, d = 0) {if (!root) return 0;
return max(getDepth(root.left, d + 1), getDepth(root.right, d + 1));
}
function dfs(root) {if (!root) return true;
if (abs(getDepth(root.left), getDepth(root.right)) > 1) return false;
return dfs(root.left) && dfs(root.right);
}
function isBalance(root) {return dfs(root);
}不难发现，这道题的后果和节点（TreeNode）的 val 没有任何关系，val 是多少齐全不影响后果。
这就完了么？
能够仔细观察题目给的应用示例，会发现题目给的是 nodes 数组，并不是二叉树的根节点 root。
因而咱们须要先 构建二叉树。 构建二叉树实质上是一个反序列的过程。要想晓得如何反序列化，必定要先晓得序列化。
而二叉树序列的办法有很多啊？题目给的是哪种呢？这须要你和面试官沟通。很有可能面试官在等着你问他呢！！！
反序列化
咱们先来看下什么是序列化，以下定义来自维基百科：
序列化（serialization）在计算机科学的数据处理中，是指将数据结构或对象状态转换成可取用格局（例如存成文件，存于缓冲，或经由网络中发送），以留待后续在雷同或另一台计算机环境中，能复原原先状态的过程。按照序列化格局从新获取字节的后果时，能够利用它来产生与原始对象雷同语义的正本。对于许多对象，像是应用大量援用的简单对象，这种序列化重建的过程并不容易。面向对象中的对象序列化，并不概括之前原始对象所关系的函数。这种过程也称为对象编组（marshalling）。从一系列字节提取数据结构的反向操作，是反序列化（也称为解编组、deserialization、unmarshalling）。
可见，序列化和反序列化在计算机科学中的利用还是十分宽泛的。就拿 LeetCode 平台来说，其容许用户输出形如：
[1,2,3,null,null,4,5]这样的数据结构来形容一颗树：
([1,2,3,null,null,4,5] 对应的二叉树)
其实序列化和反序列化只是一个概念，不是一种具体的算法，而是很多的算法。并且针对不同的数据结构，算法也会不一样。
前置常识
浏览本文之前，须要你对树的遍历以及 BFS 和 DFS 比拟相熟。如果你还不相熟，举荐浏览一下相干文章之后再来看。或者我这边也写了一个总结性的文章二叉树的遍历，你也能够看看。
前言
咱们晓得：二叉树的深度优先遍历，依据拜访根节点的程序不同，能够将其分为 前序遍历 ， 中序遍历 , 后序遍历。即如果先拜访根节点就是前序遍历，最初拜访根节点就是后序遍历，其它则是中序遍历。而左右节点的绝对程序是不会变的，肯定是先左后右。
当然也能够设定为先右后左。
并且晓得了三种遍历后果中的任意两种即可还原出原有的树结构。这不就是序列化和反序列化么？如果对这个比拟生疏的同学倡议看看我之前写的《结构二叉树系列》
有了这样一个前提之后算法就自然而然了。即先对二叉树进行两次不同的遍历，无妨假如依照前序和中序进行两次遍历。而后将两次遍历后果序列化，比方将两次遍历后果以逗号“,”join 成一个字符串。之后将字符串反序列即可，比方将其以逗号“,”split 成一个数组。
序列化：
class Solution:
def preorder(self, root: TreeNode):
if not root: return []
return [str(root.val)] +self. preorder(root.left) + self.preorder(root.right)
def inorder(self, root: TreeNode):
if not root: return []
return self.inorder(root.left) + [str(root.val)] + self.inorder(root.right)
def serialize(self, root):
ans = ''ans +=','.join(self.preorder(root))
ans += '$'
ans += ','.join(self.inorder(root))
return ans
反序列化：
这里我间接用了力扣 105. 从前序与中序遍历序列结构二叉树 的解法，一行代码都不改。
class Solution:
def deserialize(self, data: str):
preorder, inorder = data.split('$')
if not preorder: return None
return self.buildTree(preorder.split(','), inorder.split(','))
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
# 实际上 inorder 和 preorder 肯定是同时为空的，因而你无论判断哪个都行
if not preorder:
return None
root = TreeNode(preorder[0])
i = inorder.index(root.val)
root.left = self.buildTree(preorder[1:i + 1], inorder[:i])
root.right = self.buildTree(preorder[i + 1:], inorder[i+1:])
return root
实际上这个算法是不肯定成立的，起因在于树的节点可能存在反复元素。也就是说我后面说的 晓得了三种遍历后果中的任意两种即可还原出原有的树结构 是不对的，严格来说应该是 如果树中不存在反复的元素，那么晓得了三种遍历后果中的任意两种即可还原出原有的树结构。
聪慧的你应该发现了，下面我的代码用了 i = inorder.index(root.val)，如果存在反复元素，那么失去的索引 i 就可能不是精确的。然而，如果题目限定了没有反复元素则能够用这种算法。然而事实中不呈现反复元素不太事实，因而须要思考其余办法。那到底是什么样的办法呢?
答案是 记录空节点。接下来进入正题。
DFS
序列化
咱们来模拟一下力扣的记法。比方：[1,2,3,null,null,4,5](实质上是 BFS 档次遍历)，对应的树如下：
抉择这种记法，而不是 DFS 的记法的起因是看起来比拟直观。并不代表咱们这里是要讲 BFS 的序列化和反序列化。
序列化的代码非常简单，咱们只须要在一般的遍历根底上，减少对空节点的输入即可（一般的遍历是不解决空节点的）。
比方咱们都树进行一次前序遍历的同时减少空节点的解决。抉择前序遍历的起因是容易晓得根节点的地位，并且代码好写，不信你能够试试。
因而序列化就仅仅是一般的 DFS 而已，间接给大家看看代码。
Python 代码：
class Codec:
def serialize_dfs(self, root, ans):
# 空节点也须要序列化，否则无奈惟一确定一棵树，后不赘述。if not root: return ans + '#,'
# 节点之间通过逗号（,）宰割
ans += str(root.val) + ','
ans = self.serialize_dfs(root.left, ans)
ans = self.serialize_dfs(root.right, ans)
return ans
def serialize(self, root):
# 因为最初会增加一个额定的逗号，因而须要去除最初一个字符，后不赘述。return self.serialize_dfs(root, '')[:-1]Java 代码：
public class Codec {public String serialize_dfs(TreeNode root, String str) {if (root == null) {str += "None,";} else {str += str.valueOf(root.val) + ",";
str = serialize_dfs(root.left, str);
str = serialize_dfs(root.right, str);
}
return str;
}
public String serialize(TreeNode root) {return serialize_dfs(root, "");
}
}[1,2,3,null,null,4,5] 会被解决为1,2,#,#,3,4,#,#,5,#,#
咱们先看一个短视频：
（动画来自力扣）
反序列化
反序列化的第一步就是将其开展。以下面的例子来说，则会变成数组：[1,2,#,#,3,4,#,#,5,#,#]，而后咱们同样执行一次前序遍历，每次解决一个元素，重建即可。因为咱们采纳的前序遍历，因而第一个是根元素，下一个是其左子节点，下下一个是其右子节点。
Python 代码：
def deserialize_dfs(self, nodes):
if nodes:
if nodes[0] == '#':
nodes.pop(0)
return None
root = TreeNode(nodes.pop(0))
root.left = self.deserialize_dfs(nodes)
root.right = self.deserialize_dfs(nodes)
return root
return None
def deserialize(self, data: str):
nodes = data.split(',')
return self.deserialize_dfs(nodes)Java 代码：
public TreeNode deserialize_dfs(List<String> l) {if (l.get(0).equals("None")) {l.remove(0);
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(l.get(0)));
l.remove(0);
root.left = deserialize_dfs(l);
root.right = deserialize_dfs(l);
return root;
}
public TreeNode deserialize(String data) {String[] data_array = data.split(",");
List<String> data_list = new LinkedList<String>(Arrays.asList(data_array));
return deserialize_dfs(data_list);
}复杂度剖析
- 工夫复杂度：每个节点都会被解决一次，因而工夫复杂度为 $O(N)$，其中 $N$ 为节点的总数。
- 空间复杂度：空间复杂度取决于栈深度，因而空间复杂度为 $O(h)$，其中 $h$ 为树的深度。
BFS
序列化
实际上咱们也能够应用 BFS 的形式来示意一棵树。在这一点上其实就和力扣的记法是统一的了。
咱们晓得档次遍历的时候实际上是有档次的。只不过有的题目须要你记录每一个节点的档次信息，有些则不须要。
这其实就是一个朴实无华的 BFS，惟一不同则是减少了空节点。
Python 代码：
class Codec:
def serialize(self, root):
ans = ''
queue = [root]
while queue:
node = queue.pop(0)
if node:
ans += str(node.val) + ','
queue.append(node.left)
queue.append(node.right)
else:
ans += '#,'
return ans[:-1]
反序列化
如图有这样一棵树：
那么其档次遍历为 [1,2,3,#,#, 4, 5]。咱们依据此档次遍历的后果来看下如何还原二叉树，如下是我画的一个示意图：
动画演示：
容易看出：
- level x 的节点肯定指向 level x + 1 的节点，如何找到 level + 1 呢？这很容易通过档次遍从来做到。
- 对于给的的 level x，从左到右顺次对应 level x + 1 的节点，即第 1 个节点的左右子节点对应下一层的第 1 个和第 2 个节点，第 2 个节点的左右子节点对应下一层的第 3 个和第 4 个节点。。。
- 接上，其实如果你仔细观察的话，实际上 level x 和 level x + 1 的判断是无需特地判断的。咱们能够把思路逆转过去：
即第 1 个节点的左右子节点对应第 1 个和第 2 个节点，第 2 个节点的左右子节点对应第 3 个和第 4 个节点。。。（留神，没了下一层三个字）
因而咱们的思路也是同样的 BFS，并顺次连贯左右节点。
Python 代码：
def deserialize(self, data: str):
if data == '#': return None
# 数据筹备
nodes = data.split(',')
if not nodes: return None
# BFS
root = TreeNode(nodes[0])
queue = collections.deque([root])
# 曾经有 root 了，因而从 1 开始
i = 1
while i < len(nodes) - 1:
node = queue.popleft()
lv = nodes[i]
rv = nodes[i + 1]
i += 2
# 对于给的的 level x，从左到右顺次对应 level x + 1 的节点
# node 是 level x 的节点，l 和 r 则是 level x + 1 的节点
if lv != '#':
l = TreeNode(lv)
node.left = l
queue.append(l)
if rv != '#':
r = TreeNode(rv)
node.right = r
queue.append(r)
return root复杂度剖析
- 工夫复杂度：每个节点都会被解决一次，因而工夫复杂度为 $O(N)$，其中 $N$ 为节点的总数。
- 空间复杂度：$O(N)$，其中 $N$ 为节点的总数。
这样就完结了吗？
有了下面的序列化的常识。
咱们就能够问面试官是哪种序列化的伎俩。并针对性抉择反序列化计划结构出二叉树。最初再应用本文结尾的办法解决即可。
认为这里就完结了吗？
并没有！面试官让他说出本人的复杂度。
读到这里，无妨本人暂停一下，思考这个解法的复杂度是多少？
1
2
3
4
5
ok，咱们来揭秘。
工夫复杂度是 $O(n) + O(n^2)$，其中 $O(n)$ 是生成树的工夫，$O(n^2)$ 是判断是否是均衡二叉树的工夫。
为什么判断均衡二叉树的工夫复杂度是 $O(n^2)$？这是因为咱们对每一个节点都计算其深度，因而总的工夫为 所有节点深度之和，最差状况是进化到链表的状况，此时的高度之和为 $1 + 2 + … n$，依据等差数列求和公式可知，工夫复杂度是 $O(n^2)$。
空间复杂度很显著是 $O(n)$。这其中包含了构建二叉树的 n 以及递归栈的开销。
面试官又诘问：能够优化么?
读到这里，无妨本人暂停一下，思考这个解法的复杂度是多少？
1
2
3
4
5
ok，咱们来揭秘。
优化的伎俩有两种。第一种是：
- 空间换工夫。将 getDepth 函数的返回值记录下来，确保屡次执行 getDepth 且参数雷同的状况不会反复执行。这样工夫复杂度能够升高到 $O(n)$
- 第二种办法和下面的办法是相似的，其本质是记忆化递归(和动静布局相似)。
我在上一篇文章 读者：西法，记忆化递归到底怎么改成动静布局啊？具体讲述了记忆化递归和动静布局的相互转换。如果你看了的话，会发现这里就是记忆化递归。
第一种办法代码比较简单，就不写了。这里给一下第二种办法的代码。
定义函数 getDepth(root) 返回 root 的深度。须要留神的是，如果子节点不均衡，间接返回 -1。 这样下面的两个函数性能（getDepth 和 isBalance）就能够放到一个函数中执行了。
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def getDepth(root: TreeNode) -> int:
if not root:
return 0
lh = getDepth(root.left)
rh = getDepth(root.right)
# lh == -1 示意左子树不均衡
# rh == -1 示意右子树不均衡
if lh == -1 or rh == -1 or abs(rh - lh) > 1:
return -1
return max(lh, rh) + 1
return getDepth(root) != -1
总结
尽管这道面试题目是一个常见的惯例题。不过参数改了一下，霎时难度就上来了。如果面试官没有间接给你说 nodes 是怎么序列化来的，他可能是成心的。二叉树序列的办法有很多啊？题目给的是哪种呢？这须要你和面试官沟通。很有可能面试官在等着你问他呢！！！ 这正是这道题的难点所在。
结构二叉树实质就是一个二叉树反序列的过程。而如何反序列化须要联合序列化算法。
序列化办法依据是否存储空节点能够分为：存储空节点和不存储空节点。
存储空节点会造成空间的节约，不存储空节点会造成无奈惟一确定一个蕴含反复值的树。
而对于序列化，本文次要讲述的是二叉树的序列化和反序列化。看完本文之后，你就能够放心大胆地去 AC 以下两道题：
- 449. 序列化和反序列化二叉搜寻树(中等)”)
- 297. 二叉树的序列化与反序列化(艰难)”)
另外仅仅是暴力做进去还不够，大家要对本人提出更高的要求。
最起码你要会剖析本人的算法，罕用的就是复杂度剖析。进一步如果你能够对算法进行优化会很加分。比方这里我就通过两种优化办法将工夫优化到了 $O(n)$。
以上就是本文的全部内容了，大家对此有何认识，欢送给我留言，我有工夫都会一一查看答复。我是 lucifer，保护西湖区最好的算法题解，Github 超 40K star。大家也能够关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
另外我整顿的 1000 多页的电子书已限时收费下载，大家能够去我的公众号《力扣加加》后盾回复电子书获取。
