Binary Tree Tilt LeetCode solution in C++

1
/**
2
 * Definition for a binary tree node.
3
 * struct TreeNode {
4
 *     int val;
5
 *     TreeNode *left;
6
 *     TreeNode *right;
7
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
10
 * right(right) {}
11
 * };
12
 */
13
class Solution {
14
 public:
15
  /*  We will take help of recursion
16
      Each function call will return the sum of subtree with root as current
17
     root and the tilt sum will be updated in the variable passed as reference
18
  */
19

20
  int getTiltSum(TreeNode *root, int &tiltSum) {
21
    if (root == NULL) {
22
      return 0;
23
    }
24
    if (root->left == NULL and root->right == NULL) { // If we have a leaf
25
      tiltSum += 0;                                   // Add nothing to tilt sum
26
      return root->val;                               // return its value as sum
27
    }
28

29
    int leftSubTreeSum = getTiltSum(root->left, tiltSum);   // Sum of all nodes in left
30
    int rightSubTreeSum = getTiltSum(root->right, tiltSum); // and right subtrees
31

32
    tiltSum += abs(leftSubTreeSum - rightSubTreeSum); // Update the tilt sum
33

34
    // return the sum of left Subtree + right subtree + current node as the sum
35
    // of the
36
    return (root->val + leftSubTreeSum + rightSubTreeSum); // subtree with root as current node.
37
  }
38

39
  int findTilt(TreeNode *root) {
40
    // variable to be passed as refrence and store the result
41
    int tiltSum = 0;
42

43
    getTiltSum(root, tiltSum);
44

45
    return tiltSum;
46
  }
47
};