C solution, DFS 6ms with explanation.


  • 3
    H

    To compute the length of the diameter of the tree, we take the highest value of the sum of the height of the left child + 1 and the height of the right child + 1 for each node.

    However, we can avoid making this calculation for somes nodes. If a node has only one child, the diameter of hils child would be the value of the diameter of the current node -1 < current node <= diameter of the tree.

     static inline int max(int a, int b) //return the highest value of two int, usefull to compute the hight
     {
         return a > b? a :b;
     }
    static int height(struct TreeNode *t)
    {
      if(!t)
        return 0;
      return 1 + max(height(t->left), height(t->right));
    }
    
    static void dfs(struct TreeNode *root, int *maxi)
    {
        if(root)
        {
            if(root->left && !root->right)
                dfs(root->left, maxi);
            else if(root->right && !root->left)
                dfs(root->right, maxi);
            else
            {
                int hei = height(root->left) + height(root->right);
                if(hei > *maxi)
                    *maxi = hei;
                    
                dfs(root->left, maxi);
                dfs(root->right, maxi);
            }
        }
    }
    int diameterOfBinaryTree(struct TreeNode* root)
    {
        if(!root)
          return 0;
        int max;
        max = height(root->left) + height(root->right);
        dfs(root->left, &max);
        dfs(root->right, &max);
        return max;      
    }
    
    

  • 2
    D

    you should use a define for the max (as it's valid for any simple type):

    #define MAX(X,Y) ( ((X)>(Y)) ? (X) : (Y))
    

  • 0
    H

    @D0tty said in C solution, DFS 6ms with explanation.:

    #define MAX(X,Y) ( ((X)>(Y)) ? (X) : (Y))

    Haha thank you for the protip.


Log in to reply
 

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