• Given a binary tree, calculate the slope of the entire tree.
• The slope of a node of a tree is defined as the absolute value of the difference between the sum of the nodes of the left subtree and the sum of the nodes of the right subtree.
• If there is no left subtree, the sum of the nodes of the left subtree is 0; Same thing if there’s no right subtree. The slope of the null node is 0. The slope of a tree is the sum of the slopes of all its nodes.

The sample a

Input: root = [1, 2, 3] output: 1: node 2 grade: | | 0-0 = 0 (no children) node 3 grade: | | 0-0 = 0 (no children) the slope of node 1: | 3 | = 1 (left subtree is left child node, and so is 2; The right subtree is the right subnode, so the sum is 3) slope sum: 0 + 0 + 1 = 1Copy the code

Example 2

Input: root = [4,2,9,3,5, null, 7] output: 15: node 3 grade: | | 0-0 = 0 (no children) node 5 slope: | | 0-0 = 0 (no children) node 7 grade: | 0-0 | = 0 (no children) node 2 grade: | | 3-5 = 2 (left subtree is left child node, and so is 3; Right subtree is right child nodes, and so is 5) node 9 slope: | | 0 to 7 = 7 (no left subtree, and so is 0; Right subtree is right child nodes, and so is 7) node 4 grade: | (3 + 5 + 2) - (9 + 7) | | = | 10 to 16 = 6 (left subtree value of 3, 5, and 2, and is 10; The right subtree values are 9 and 7, and the sum is 16) Slope sum: 0 + 0 + 0 + 2 + 7 + 6 = 15Copy the code

Train of thought

• First of all, we can see from the example
  • Is the absolute value of the difference between traversing each node and summing up the left and right subtrees
  • And finally we return all of themslopeThe sum of the
• So let’s keep iterating through the left subtree to get the sum of the left subtree

  • The same goes for the right subtree, but the absolute difference between the sum of the left and right subtrees is added to the RES

  • The terminating node is traversal empty

  • The condition for entering the next level is the sum of the left and right subtrees of the root node plus the value of that node

class Solution {
    int res = 0;
    public int findTilt(TreeNode root) {
        dfs(root);
        return res;
    }

    public int dfs(TreeNode node) {
        if (node == null) return 0;
        int leftRes = dfs(node.left);
        int rightRes = dfs(node.right);
        
        res += Math.abs(leftRes - rightRes);
        returnleftRes + rightRes + node.val; }}Copy the code