[C++] [LeetCode 543] Diameter of Binary Tree

[C++] [LeetCode 543] Diameter of Binary Tree

728x90

문제 풀기 전 생각 :

/* 재귀함수의 형식으로 문제를 풀기로 결정했다 res에 제일 깊은 깊이값을 저장하고 리턴할 때 해당 노드가 비어있지 않다면 해당 함수가 리턴받은 값에서 가장 큰 값에 1을 더한후 리턴한다 그리고 리턴받은 left 값과 right 값을 더한 값이 res와 비교해 더욱 큰 값을 res에 넣는다. */

class Solution { public: int diameterOfBinaryTreeUtil(TreeNode* root, int &res;) { if(root == NULL) return 0; int l = diameterOfBinaryTreeUtil(root->left, res); int r = diameterOfBinaryTreeUtil(root->right, res); res = max(l + r, res); return max(l, r) + 1; } int diameterOfBinaryTree(TreeNode* root) { int res = 0; diameterOfBinaryTreeUtil(root, res); return res; } };

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

풀 때 어려웠던 점 또는 느낀점 :

트리 관련 문제가 처음에는 복잡했지만

문제를 풀수록 조금씩 익숙해지는듯 해

기쁘다

개선방안 :

class Solution { public: int getDia(TreeNode* root, int& sum){ if(!root) return 0; int lst = getDia(root->left, sum); int rst = getDia(root->right, sum); sum = max(sum, (1 + lst + rst)); return 1 + max(lst , rst); } int diameterOfBinaryTree(TreeNode* root) { if(!root) return 0; int sum = 0; getDia(root, sum); return sum - 1; } };

같은 접근법인것 같다.

from http://365waytobe-pro-grammer.tistory.com/79 by ccl(A) rewrite - 2021-08-09 19:00:29