Time: 15 minutes

Time: 15 minutes

My first reaction when I got the question was to use recursion, but after I started writing it, I found that

The condition that recursion needs to meet is that the problem can be split into sub-problems, but according to the meaning of the question, what we need to find is the difference between the sum of the left and right nodes of each node. This “sum of the left and right nodes” is a different problem for each node.

So it’s still double recursion

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!!!!!!!!

After looking at the answer, I think I should just take the clothes.

It turns out that calculating the sum of the left and right nodes is not inconsistent with accumulating the difference between the left and right nodes. A recursive operation can solve the problem. When performing DFS, we can do both at the same time. The accumulation of the left and right nodes is return root.val + left + right, and the difference is total += Math.abs(left-right)

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
};

I am still young, I have done similar recursion