Binary Tree Tilt


  • 0

    Click here to see the full article post


  • 0
    I

    why can't i view the question from this article? It says access denied.

    https://leetcode.com/problems/binary-tree-tilt/
    403: Access denied


  • 0
    A

    what is the pictorial binary tree representation of [1,2,3,4,null,5]? and, what is the explanation of its tilt?


  • 0

    @ardey16 Tilt=4+5+(8-6)=11

    
         1
        /  \
      2    3
     /     /
    4     5
    

  • 0
    K

    why is it 4+5+(8-6)? shouldnt it be 1+(8-6)=3 ?


  • 0

    @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


  • 0
    Z
        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;
        }
    

  • 0
    M

    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);
        }

  • 0
    R

    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);
        }
    };
    

  • 0
    Y

    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.


  • 0
    C

    Did the exact thing in python. Hurrah


  • 0
    J

    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);
    

    }


  • 0
    J

    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.


  • 0
    Z

    Ugly solution with the use of helper field. Doesn't support multiple calls, not thread safe etc. It seems number of lines is the only criteria of success on leetcode instead of readability and maintainability


  • 0
    G

    Doesn't work for [1,2].


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.