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

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

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

문제 내용

트리의 지름을 구하는 문제

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); } };

from http://bluespacedev.tistory.com/78 by ccl(A) rewrite - 2021-10-11 12:01:00