Siqi Liu Yosgi

用时 ：30min 看懂题目的意思之后其实就能很快的做出来 题意是要求从任意节点出发的值，我们可以把每个节点的值求出来的过程中，选择最大的 又因为路径不能返回，可以知道我们出发的根节点的子节点的路径只能选择左或者右，或者都不要，结果为 x 求max 的时候再 把 x 和 左右都选的情况进行比较 var maxPathSum = function(root) { var max = …

用时：80min 拿到题的第一个反应当然是DFS解决…. 但是这是一个完全二叉树，怎么说也应该把完全二叉树的性质用上才行 可以考察二叉树的左右子树深度 如果左深度 大于 右 ， 说明右边已经满了，满了的个数是 2 的 n 次方 - 1，加上root 是 2 的 n次方，继续递归左边 如果右深度大于左， 说明左边满了，同样，继续递归右边 至于怎么求二叉树的深度，可以从下往上递归 var count …

用时：120min 一开始的思路是用BFS，出队时出一整队（后来知道这叫宽度遍历） 然后双指针找到左右节点。当左右节点都不存在时结束 var widthOfBinaryTree = function(root) { var que = [root] var max = 0 while(que.length) { var len = que.length var left = 0 var right …

用时 10min 直接用二叉搜索树中序遍历递增的性质就好了 中序遍历找到左孩子 pre 是否存在 不存在，赋值 ，找右孩子，返回 1 存在，是否比 val 小 是，非递增，返回 false 否，递增，赋值 pre ，返回 1 var isValidBST = function(root) { var preVal = null var DFS = function(root) { var left …

用时：60min 思路还是中序遍历，使用pre缓存前一个节点，因为中序遍历是递增的，所以一定是先找到大的，再找到小的。 所以第一个出问题的是pre，第二个是root var recoverTree = function(root) { var left = null var right = null var pre = null // 一定是先找到大的，再找到小的，所以第一个出问题的是pre，第二 …

用时: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 …