why can't i view the question from this article? It says access denied.
https://leetcode.com/problems/binary-tree-tilt/
403: Access denied
what is the pictorial binary tree representation of [1,2,3,4,null,5]? and, what is the explanation of its tilt?
@kekondur
tilt of 4 - 0
tilt of 2- (4-0=4)
tilt of 5- 0
tilt of 3- (5-0=5)
tilt of 1- (8-6=2)
total tilt- 0+4+0+5+2=11
pair<int,int> FindSumTilt(TreeNode* root){
if(root == nullptr){
return make_pair(0,0);
}
auto left_res = FindSumTilt(root->left);
auto right_res = FindSumTilt(root->right);
int sum = left_res.first + right_res.first + root->val;
int tilt = left_res.second + right_res.second + abs(left_res.first - right_res.first);
return make_pair(sum,tilt);
}
int findTilt(TreeNode* root) {
if(root == nullptr){
return 0;
}
auto res = FindSumTilt(root);
return res.second;
}
Less then 10 lines C# code
public int FindTilt(TreeNode root)
{
if (root == null)
return 0;
return Math.Abs(SumNode(root.left) - SumNode(root.right)) + FindTilt(root.left) + FindTilt(root.right);
}
int SumNode(TreeNode node)
{
if (node == null)
return 0;
return node.val + SumNode(node.left) + SumNode(node.right);
}C++ solution O(n)
class Solution {
public:
// tiltDFS returns sum and accumulate tilt of each node
int tiltDFS(TreeNode *root, int &tilt)
{
if (!root)
return 0;
// Traverse left
int sumLeft = tiltDFS(root->left, tilt);
// Traverse right
int sumRight = tiltDFS(root->right, tilt);
// Calculate current tilt and add to total tilt
tilt += abs(sumLeft - sumRight);
// return sum of node values up to this node
return (sumLeft + sumRight + root->val);
}
int findTilt(TreeNode *root)
{
if (!root)
return 0;
int TL, TR, SR, SL;
TL = TR = SL = SR = 0;
// Get left tilt and sum of left nodes
SL = tiltDFS(root->left, TL);
// Get right tilt and sum of right nodes
SR = tiltDFS(root->right, TR);
// Return total tilt
return (abs(SR - SL) + TL + TR);
}
};
Something is not correct either in the question or the answer. The question states that the tilt is: "The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values". With that definition, tilt of root will be |sum(left) - sum(right)|. However this answer states that the root's tilt is root.val + |sum(left) - sum(right)|. Please advise if I am missing something here.
JS without global variable:
var findTilt = function(root) {
return treeTilt(root, { val: 0 });
};
var treeTilt = function(root, sum) {
if (root === null) {
return 0;
}
var leftSum = { val: 0 };
var rightSum = { val: 0 };
var leftTilt = treeTilt(root.left, leftSum);
var rightTilt = treeTilt(root.right, rightSum);
sum.val = root.val + leftSum.val + rightSum.val;
return leftTilt + rightTilt + Math.abs(leftSum.val - rightSum.val);
}
Everybody knows the recursive - the trick is in the return statement: (left+right+val) -- it's not the tilt but return value. Actually it covers every situations of a given note - it works. But nobody explains or even mention it in their solution.