Leetcode - 543. Diameter of Binary Tree

문제

주어진 이진트리의 Diameter(트리 내 존재하는 두 노드의 path중 가장 긴 path)를 구하라

https://leetcode.com/problems/diameter-of-binary-tree/

해결 O(N)

처음 접하는 유형의 문제였다. 단순히 루트노드에서 왼쪽깊이, 오른쪽깊이 두개를 더하면 오답이 나온다. 루트 이하 노드에서 더 긴 path가 나올 수도 있기 때문. 가령 아래같은 트리의 경우 root의 경우 최대길이는 1 + 5(왼쪽,오른쪽길이합) 이지만. root->right노드의 경우 4+4로 더 크다. 따라서 모든 노드를 순회하면서 노드마다 현재 노드의 max값을 갱신 하는 방식으로 풀어야한다.

    o
 o     o
     o   o
   o    o  o
 o           o 
  o        o
  

그리고 트리순회의 시간복잡도는 N개의 노드를 한번씩 방문하므로 O(N)이다. 재귀호출이 2번일어난다고 O(2^N)이 아니다.

#define max(a,b)    (((a) > (b)) ? (a) : (b))
int max_val;
int max_depth(struct TreeNode *node)
{
    if (node == NULL)
        return 0;
    int L = max_depth(node->left);
    int R = max_depth(node->right);
    if (L + R > max_val)
        max_val = L + R;
    return max(L, R) + 1;
}
int diameterOfBinaryTree(struct TreeNode* root){
    max_val = 0;
    max_depth(root);
    return max_val;
}