Yosgi Yosgi

用时： 偷偷看了答案 本来把问题想复杂了，想着维护一个最大堆，从上往下传递然后每次判断是否大于最大值 看了答案后发现只需要传递一个max，判断是否比max大，然后从下到上获取左右节点的值，返回左右节点和 加自身是否符合就好了 var goodNodes = function(root,max = root.val) { if (!root) return 0 var left = 0 max = …

用时：6min 很简单，中序遍历，计算两边子树是否存在 1 的值，没有就去掉。凡事左右子树或者自身包含 1 ，返回 true 。否则返回 false var pruneTree = function(root) { var DFS = function (root) { if (!root) return false var left = DFS(root.left) var right = …

看题型是求从根节点出发的，首先想到的是自顶向下的DFS，带着参数向下传递，结束条件没有左右儿子 直接前序遍历走起，可以认为是前面的节点都处理好了 var sumNumbers = function(root) { var ans = 0 var DFS = function (root,path) { if (!root) return path += root.val if …

用时：15min 用时：15min 拿到题的第一反应是是用递归，然后直接开始写了后发现 递归需要满足的条件是问题可以拆分成子问题，但是根据题意，我们需要求的是每个节点左右节点和的差值，这个 “左右节点和” 对于每个节点来说，都是不一样的问题 所以还是双递归 var findTilt = function(root) { var total = 0 var innerDFS = function …

用时：20min 因为是求 ” 每个节点出发的为sum的路径” 很明显就想到了回溯，因为是二叉树，所以就双递归。 外层递归用来找到所有的节点，内层用来算节点的路径 var pathSum = function(root, sum) { var res = 0 var dfs = function (root,total,visited) { if (!root) return if (total …

用时 ：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，第二 …