Yosgi Yosgi

用时：30min 序列化很简单，使用BFS可以解决 反序列化需要用到二叉树的性质，即第 i 个节点的子节点分别为 (i + 1) * 2 - 1 和 ( i + 1) * 2, 流程 找到父节点，入栈，此时指针 i 在 父节点的 val 上 父节点出栈，找到父节点的左右节点，指针根据规则找到 两遍的值，左右节点入栈， i++ 重复 1 var serialize = function(root) …

用时：25min 其实是比较常规的DFS类型题目，之所以用这么久是因为对边界值的判断出了问题。 从 root 出发时， 因为root 是可能没有子节点的，所以 len 值 为 0 从子节点出发，因为已经判断完字节点，算作当前节点到下一节点已经走一条长度为 1 的边 ， 所以是 1 var longestZigZag = function(root) { // true left false …

102.二叉树的层序遍历 遍历本身很简单，需要考虑的问题是怎么标示每一层，这里可以用迭代和递归两种思路 迭代 入队 root ，再入队一个null 表示第 0 层的结束 出队 root ，入队左右节点 ， 如果出队的是null，说明一层结束，再入队一个 null 队列不为空，循环 2 ⚠️ 需要注意的点： 队列最后一项如果不做处理将会一直是null，因此需要增加结束条件 var …

为什么前中后序遍历用栈，而层序遍历使用队列 ？ 二叉树的前中后序遍历的迭代时，我们用栈来简化操作，因为它们都是DFS的递归结构，也就是从下到上处理，但是我写代码一定是从root节点开始，所以需要栈，而栈正好是先进先出的。这样我才可以把处理root放在最后。 层序遍历是BFS，由上至下。最先入队的root也是我想最先处理的。这就是为什么DFS 使用栈而BFS使用队列的原因。 DFS的算法流程与模板 …

二叉树前中后序遍历总结 从前面的题目中可以看到，二叉树的前中后序遍历的递归方法是类似的，但是迭代的实现完全不同。 从垃圾回收的三色标记法得到启发，发现他们的共同点 节点入栈，标记为 0 （ 未访问 ） 节点出栈，若已经访问，出栈。若未访问，标记为已访问，入栈。 节点左右节点 继续到 1 这样，我们可以通过控制节点的入栈顺序，用相似的代码来迭代完成二叉树的前中后序遍历。需要额外做的是多开一个On的空 …

145.二叉树的后序遍历 1h 中序遍历的顺序是 左 - 右 - 中 递归 用递归非常容易 var postorderTraversal = function(root) { var res = [] if (!root) return res var travel = function (node) { node.left && travel(node.left) node.right && …

144.二叉树的前序遍历 10min 二叉树的前序遍历的顺序是中 - 左 - 右 先遍历完所有的根节点与左节点，然后处理右节点 可以看出来这是一个递归的行为，递归问题可以用栈来进行简化 迭代解法 var preorderTraversal = function(root) { if (!root) return null var stack = [root] var res = [] …

94.二叉树的中序遍历 30min 中序遍历的顺序是 左 - 中 - 右 递归 用递归非常容易 var inorderTraversal = function(root) { var res = [] if (!root) { return res } var travel = function (node) { node.left && travel(node.left) …

递归 前序遍历：中-左-右 中序遍历：左-中-右 因此可以先从前序遍历找到根元素，再由中序确定左右子树的个数 var buildTree = function(preorder, inorder) { if (preorder.length === 0 || inorder.length=== 0) return null let nodeVal = preorder.shift() let …