A simple C solution


  • 0
    B

    Pre-order by Recursion [Accpeted]
    Intuition

    1. For solving this problem. we need a Pre-order to traversal the binary tree.
    2. We need to make a record of depth when traversal the binary tree.
    3. Each time traversal in leaf node, read the depth and store the bigger one.
    4. At last, we can get the result of maximum depth.

    Algorithm

    1. Use the Pre-order algorithm.
    2. Use temp to recode depth constantly.
    3. Determine whether the current node is a leaf node. If yes and temp bigger than result(result's initial value is 0), do result=temp.

    C

    int temp;
    int result;
    void PreOrder(struct TreeNode* root)
    {
        if(root==NULL) return;
        temp++;
        if(root->left==NULL&&root->right==NULL)
        {
            if(result<temp)
                result=temp;
        }
        PreOrder(root->left);
        PreOrder(root->right);
        temp--;
    }
    int maxDepth(struct TreeNode* root) {
        result=0;
        temp=0;
        PreOrder(root);
        return result;
    }
    

    Complexity Analysis

    • Time complexity: O(n)
      Just like a pre-order traversal.
    • Space complexity: Who can tell me the space complexity?

Log in to reply
 

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