563. 二叉树的坡度

发表于 | 分类于
简单题目

用时：15min

用时：15min

拿到题的第一反应是是用递归，然后直接开始写了后发现

递归需要满足的条件是问题可以拆分成子问题，但是根据题意，我们需要求的是每个节点左右节点和的差值，这个 “左右节点和” 对于每个节点来说，都是不一样的问题

所以还是双递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var findTilt = function(root) {
    var total = 0
    var innerDFS = function (root) {
        if (!root) return 0
        var left = 0 ,right = 0
        if (root.left) {
            left = innerDFS(root.left) 
        }
        if (root.right) {
            right = innerDFS(root.right)
        }
        return root.val + left + right
    }
    var outerDFS = function (root) {
        if (!root) return
        root.right && outerDFS(root.right)
        total += Math.abs(innerDFS(root.left) - innerDFS(root.right))
        root.left && outerDFS(root.left)
    }
    outerDFS(root)
    return total
};

But!!!!!!!!

看了一眼答案我觉得自己还是拿衣服了

原来计算左右节点之和，与累积左右节点只差并不矛盾，一个递归就能解决问题。就是DFS的时候顺便两者一起做了，累计左右节点就是 return root.val + left + right 而计算差值是 total += Math.abs(left-right)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var findTilt = function(root) {
    var total = 0
    var DFS = function (root) {
        if (!root) return 0
        var left = 0 ,right = 0
        if (root.left) {
            left = DFS(root.left) 
        }
        if (root.right) {
            right = DFS(root.right)
        }
        total += Math.abs(left-right)
        return root.val + left + right
    }
    DFS(root)
    return total
};

还是年轻了，明明做过类似的递归