Slope of binary tree

563. The slope of the binary tree

The difficulty is simple 274

Give you the root node of a binary tree root , Calculate and return The whole tree Slope of .

A tree's The slope of the node The definition is , The sum of the nodes of the left subtree and the sum of the nodes of the right subtree of the node The absolute value of the difference . If there is no left subtree , The sum of the nodes of the left subtree is 0 ; It's the same without the right subtree . The slope of the empty node is 0 .

The whole tree The slope of a node is the sum of the slopes of all nodes .

Example 1：

 Input ：root = [1,2,3]
 Output ：1
 explain ：
 node  2  Slope of ：|0-0| = 0（ No child node ）
 node  3  Slope of ：|0-0| = 0（ No child node ）
 node  1  Slope of ：|2-3| = 1（ The left subtree is the left child node , So and are  2 ; The right subtree is the right child node , So and are  3 ）
 Slope sum ：0 + 0 + 1 = 1

Example 2：

 Input ：root = [4,2,9,3,5,null,7]
 Output ：15
 explain ：
 node  3  Slope of ：|0-0| = 0（ No child node ）
 node  5  Slope of ：|0-0| = 0（ No child node ）
 node  7  Slope of ：|0-0| = 0（ No child node ）
 node  2  Slope of ：|3-5| = 2（ The left subtree is the left child node , So and are  3 ; The right subtree is the right child node , So and are  5 ）
 node  9  Slope of ：|0-7| = 7（ There is no left subtree , So and are  0 ; The right subtree is exactly the right child node , So and are  7 ）
 node  4  Slope of ：|(3+5+2)-(9+7)| = |10-16| = 6（ The left subtree value is  3、5  and  2 , And is  10 ; The right subtree value is  9  and  7 , And is  16 ）
 Slope sum ：0 + 0 + 0 + 2 + 7 + 6 = 15

Example 3：

 Input ：root = [21,7,14,1,1,2,2,3,3]
 Output ：9

Tips ：

• The number of nodes in the tree ranges from [0, 104] Inside
• -1000 <= Node.val <= 1000

---

Ideas ： Depth-first search （DFS）

First of all, understand the meaning of the title , We want to accumulate the absolute value of the difference between the sum of left subtree nodes and the sum of right subtree nodes of all nodes of the binary tree . therefore , We can use Depth-first search , When traversing each node , Accumulate the absolute value of the difference between the sum of the left subtree nodes and the sum of the right subtree nodes , And return the sum of the nodes of the tree with it as the root node .

• So let's create one Global variables sum Used to accumulate the sum of the absolute values of each node , Then create a sub function , To subfunction _find() De recursion .
• use left and right Recursively get the values of the left subtree and the right subtree respectively , And then use sum Plus the difference between their absolute values .
• Return to root The sum of the nodes of the tree as the root node left + right + root->val

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
public:
    int sum = 0;
    int _find(TreeNode* root)
    {
    
        if(root == nullptr)
            return 0;

        int left = _find(root->left);
        int right = _find(root->right);
        sum += abs(left - right);
        return root->val + left + right;
    }
    int findTilt(TreeNode* root) {
    
        _find(root);
        return sum;
    }
};

Complexity analysis

Time complexity ：O(n), among n Is the total number of nodes in the binary tree

Spatial complexity ：O(n)