[Leetcode] 543. Diameter of Binary Tree

1. 문제링크

Diameter of Binary Tree - LeetCode

- Diameter : 지름

binary tree에서 제일 긴 path의 길이를 구한다

이 path는 특정노드에 대해서 가장 왼쪽 edge node  -> 오른쪽 edge 노드까지의 길이이다

 

 

2. Key point -  현재 노드의 maxLength를 리턴하고, maxDia는 매번 갱신한다

문제에서 path는 root노드를 pass하지 않아도 되는 조건이 있다.

1번 노드(빨강)의 longest path는 [6, 4, 2, 1, 3]이고 diameter는 4이다

2번 노드(노랑)의 longest path는 [6, 4, 2, 5, 7, 8]이고 diameter는 5이다

이 tree node에서 가장 긴 diameter를 구하는 문제이므로 정답은 5가 된다.

 

 

3. solution

class Solution {
public:
    int maxDia = 0;
    int getLength(TreeNode* root){
        if(!root)
            return 0;
        int left = getLength(root->left);
        int right = getLength(root->right);
        maxDia = max(maxDia, left + right);
        return max(left, right) + 1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        getLength(root);
        return maxDia;
    }
};