Given the root of a binary tree, return the sum of every tree node's tilt.

The tilt of a tree node is the absolute difference between the sum of all left subtree node values and all right subtree node values. If a node does not have a left child, then the sum of the left subtree node values is treated as 0. The rule is similar if the node does not have a right child.

&nbsp;
Example 1:

Input: root = [1,2,3]
Output: 1
Explanation: 
Tilt of node 2 : |0-0| = 0 (no children)
Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)
Sum of every tilt : 0 + 0 + 1 = 1


Example 2:

Input: root = [4,2,9,3,5,null,7]
Output: 15
Explanation: 
Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 5 : |0-0| = 0 (no children)
Tilt of node 7 : |0-0| = 0 (no children)
Tilt of node 2 : |3-5| = 2 (left subtree is just left child, so sum is 3; right subtree is just right child, so sum is 5)
Tilt of node 9 : |0-7| = 7 (no left child, so sum is 0; right subtree is just right child, so sum is 7)
Tilt of node 4 : |(3+5+2)-(9+7)| = |10-16| = 6 (left subtree values are 3, 5, and 2, which sums to 10; right subtree values are 9 and 7, which sums to 16)
Sum of every tilt : 0 + 0 + 0 + 2 + 7 + 6 = 15


Example 3:

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


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [0, 104].
	-1000 &lt;= Node.val &lt;= 1000


# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def findTilt(self, root: Optional[TreeNode]) -> int:
        res = [0]
        def tilt_helper(root,res):
            if not root:
                return 0

            left = tilt_helper(root.left,res)
            right = tilt_helper(root.right,res)

            res[0] += abs(left-right)

            return left + right + root.val

        tilt_helper(root,res)
        return res[0]
class Solution {
    int max = 0;
    public int findTilt(TreeNode root) {
        loop(root);
        return max;
    }
    public int loop(TreeNode root){
        if(root==null) return 0;
        int left = loop(root.left);
        int right = loop(root.right);
        max+= Math.abs(left-right);
        return root.val+left+right;
    }
}
/**
 * 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:
    
    /*  We will take help of recursion
        Each function call will return the sum of subtree with root as current root
        and the tilt sum will be updated in the variable passed as reference
    */
    
    int getTiltSum(TreeNode* root, int &tiltSum){
        if(root == NULL){
            return 0;
        }
        if(root->left == NULL and root->right == NULL){     // If we have a leaf
            tiltSum+=0;         // Add nothing to tilt sum
            return root->val;   // return its value as sum
        }
        
        int leftSubTreeSum = getTiltSum(root->left, tiltSum);   // Sum of all nodes in left
        int rightSubTreeSum = getTiltSum(root->right, tiltSum); // and right subtrees
        
        tiltSum += abs(leftSubTreeSum - rightSubTreeSum);   // Update the tilt sum
        
        // return the sum of left Subtree + right subtree + current node as the sum of the 
        return (root->val + leftSubTreeSum + rightSubTreeSum);  // subtree with root as current node.
        
    }
    
    
    int findTilt(TreeNode* root) {
        // variable to be passed as refrence and store the result
        int tiltSum = 0;
        
        getTiltSum(root, tiltSum);
        
        return tiltSum;
    }
};
var findTilt = function(root) {
    function helper(node, acc) {
        if (node === null) {
            return 0;
        }

        const left = helper(node.left, acc);
        const right = helper(node.right, acc);

        acc.sum += Math.abs(left - right);

        return left + node.val + right;
    }

    let acc = { sum: 0 };
    helper(root, acc);

    return acc.sum;
};
Binary Tree Tilt