Yosgi Yosgi

用时:30min 题目分两个部分需要解决，搜索和删除 搜索部分就是找到节点，可以根据二叉搜索树的性质来找到需要的节点 删除分三种情况 只有左孩子，用左孩子代替 只有右孩子，用右孩子代替 都没有，则赋值为null （ 由于前面有递归赋值，所以这边可以成功 都有，则储存左孩子后，用右孩子代替，然后找到左孩子在右边的位置 var deleteNode = function(root, key) { …

用时 ：20min 与上一道题类似，多的是分了父节点在区间内和不在区间内的情况 var trimBST = function(root, low, high) { var add = function (root,node) { if (!node || !root) return null if (node.val > root.val ) { if (!root.right) { …

用时 ： 没做出来 没做出来的主要原因是一直想着怎么用栈来做，写到后面看栈的答案看着看着发现递归最简单 递归 思路很简单，首先写出来怎么插入子节点 如果比父节点小，且父节点左为空，直接做左节点 如果比父节点大，且父节点右为空，直接做右节点 比父节点小，则父节点赋值为父节点的左节点，回到 1 比父节点大，则父节点赋值为父节点的右节点，回到1 遍历整个数组，一个个插入即可得到结果 var …

用时 ：25min 主要思路是利用栈，和普通的层序遍历不同的是每次都把栈清空 var connect = function(root) { if (!root) return null var stack = [root] while(stack.length) { var _stack = [...stack,null] stack = [] var pre = _stack.shift() …

用时： 抄答案才做出来 思路很容易看出来是利用递归，但是coding才是真正的问题。 我们需要返回的是根节点，但是递归是从下至上的 尝试用动态规划解决，dp(n) 是 dp(x) 与 dp (n - x - 1) 结果的组合 var allPossibleFBT = function(n) { var dp = [] var buld = function (n) { for(let i = 1 …

用时：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的空 …