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

---

문제 풀기 전 생각 : 

/*
재귀함수의 형식으로 문제를 풀기로 결정했다
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/

Diameter of Binary Tree - LeetCode

---

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

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

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

기쁘다

 

---

개선방안 :

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

같은 접근법인것 같다.