[leetcode 543] Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

 

 

 

 

 

 

트리 지름 구하기. 같은 부모를 가진 노드 사이에 최대 거리 구하기

 

문제 풀이

- 항상 루트 노드를 지나야 최대 거리라고 생각해서 틀림!

- 루트 노드를 지나지 않아도 최대 거리일 수 있다.

- 따라서 매 노드마다 diameter를 구해줘야 한다.

- 매번 diameter를 새로 구하기 보다는 중복된 이전 단계의 diameter를 빼줘서(-diameter*2) 최대 값을 구한다.

 

/**
 * 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 answer;
    
    //현재 노드에서 얻을 수 있는 최대 diameter를 구한다.
    int calDis(TreeNode *cur, int dia){
        
        if(cur == nullptr){
            return dia -1;
        }
        
        int leftDis = calDis(cur->left, dia+1);
        int rightDis = calDis(cur->right, dia+1);
        
        
        //부모 노드의 diameter를 빼준다. 중복이니깐
        answer = max(answer , leftDis+rightDis - 2*dia);
        
        return max(leftDis, rightDis);
    }
  
    int diameterOfBinaryTree(TreeNode* root) {
        
        if(root == nullptr){
            return 0;
        }
        
        answer = 0;
        calDis(root, 1);
     
       return answer;
        
    }
};