[Leetcode] 543. Diameter of Binary Tree 문제풀이

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

Diameter of Binary Tree - LeetCode

 

문제 내용

트리의 지름을 구하는 문제

 

Example 1:

Input: root = [1,2,3,4,5]

Output: 3

Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

 

문제 풀이

트리의 지름을 구하기 위해서는 양쪽 자식의 깊이를 더했을 때 가장 큰 값을 구하면 된다.

먼저 깊이를 구해서 val에 저장했고

그 다음 하나씩 노드를 탐색하면서 지름이 가장 큰 값을 구했다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int length(TreeNode* node) {
        if (node == nullptr)
            return 0;
        
        int ans = 0;
        if (node->left != nullptr)
            ans += node->left->val + 1;
        if (node->right != nullptr)
            ans += node->right->val + 1;
        
        return max(ans, max(length(node->left), length(node->right)));
    }
    int depth(TreeNode* node) {
        int ans = 0;
        if (node->left != nullptr)
            ans = depth(node->left) + 1;
        if (node->right != nullptr)
            ans = max(ans, depth(node->right) + 1);
        
        return node->val = ans;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        if (root == nullptr)
            return 0;
        
        depth(root);
        
        return length(root);
    }
};