LeetCode[day11] - 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.

Note:
 The length of path between two nodes is represented by the number of edges between them

 

 

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 우선, 해당 문제는 이진 트리가 input으로 주어진다.

 - 이진트리란 무엇일까? 이진트리는 각각의 노드가 최대 2개의 자식 노드를 갖는 자료구조라고 한다.

 트리의 용어로는 차수(degree), 깊이(depth), 레벨(level), 높이(height), 크기(size)등이 있다.

• degree : 노드의 자식의 수를 의미한다.
• depth : 루트 노드에서 자식 노드까지 가는 길이를 의미한다. 루트노드는 0이다.
• level : 루트 노드에서 자식 노드까지 가는 길이에 1을 더한 값을 레벨이라고 한다.
• height : 노드와 단말 노드간의 최대 길이이다.
• size : 자기 자신 및 자식 노드의 합의 수이다.

- 그래서, 다시 돌아와서 문제에서는 특정 노드와 특정 노드간의 가장 긴 길이를 구하라는 문제였다.

가장 루트 노드를 기준으로 생각을 하게 되었다. left, right로 이동하게 될 때 재귀함수를 이용해서, 가장 마지막 메소드가 호출 될 때 maxDepth를 구한다. 이 때, 다시 left와 right로 분기가 될 것이니, 그것에 대한 maxDepth를 Math.max()로 구한다.

- 이렇게 됐을 때는 루트 노드를 기준으로 이동하기 때문에 특이 케이스가 나타났었다. 

 

2. 알고리즘 작성 중, 어려운 점

 

 - 우선, 내 알고리즘의 로직은 부모 노드를 기준으로 생각을 하고 있다.

 - 항상, 부모노드를 기준으로 왼쪽의 최대 길이와 오른쪽의 최대 길이를 더하는 값을 결과로 하고 있다. 

 

3. 내가 작성한 알고리즘

 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int depthMax = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        int depth = 0;
        int maxDepth = 0;
        int maxDepth2 = 0;
        if(root != null){
            if(root.left!= null){
                maxDepth = exploreTree(root.left, 1);        
            }
            if(root.right != null){
                maxDepth2 = exploreTree(root.right, 1);    
            }
            System.out.println(maxDepth);
            System.out.println(maxDepth2);
        }
        
        return maxDepth + maxDepth2;
    }
    
    private int exploreTree(TreeNode treeNode, int depth){
        int maxDepth = depth;
        if(treeNode != null && treeNode.left != null){
            int returnDepth = exploreTree(treeNode.left, depth+1);
            maxDepth = Math.max(maxDepth, returnDepth);
            System.out.println("MaxDepth:"+ maxDepth);
        }
        if(treeNode != null && treeNode.right != null){
            int returnDepth = exploreTree(treeNode.right, depth+1);
            maxDepth = Math.max(maxDepth, returnDepth);
            System.out.println("MaxDepth:"+ maxDepth);
        }
        
        return maxDepth;
    }
}

 

5. 다른 사람이 작성한 알고리즘 보기

 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int maxDiameter = 0;
    
    public int diameterOfBinaryTree(TreeNode root) {
        getDiameter(root);
        return maxDiameter;
    }
    
    private int getDiameter(TreeNode node){
        if(node == null){
            return 0;
        }
        int leftHeight = getDiameter(node.left);
        int rightHeight = getDiameter(node.right);
        maxDiameter = Math.max(maxDiameter ,rightHeight+leftHeight);
        return Math.max(leftHeight, rightHeight) + 1;
    }   
}

 

6. 다른 사람이 작성한 알고리즘을 보고 배운점

 - 우선, 알고리즘을 작성할 때 마지막 노드를 기준으로 생각을 하면, 시각이 조금 트이는 느낌이 들었다.

 - 마지막 노드는 getDiameter()기준으로, leftHeight과 rightHeight이 없다. 그래서 무조건, 1값을 추가로 해준다.

 - 첫 번째 return의 의미는 1씩 누적하는 의미가 담겨져 있다.

 - 두 번쨰 return의 의미는 left와 right를 더한 값에 +1을 해서 현재 기준으로 좌우 직경이 가장 긴 길이를 돌려준다.

 - 그리고, 재귀함수에서 getDiameter() 메소드는 return을 통해, 좌우 직경이 가장 긴 길이를 받게 된다.

 - 그렇게 된다면, getDiameter() 메소드는 해당 메소드가 호출 된 시점에서 left,right의 가장 긴 길이를 받을 수 있다.

 - 따라서, 항상 root를 거치지 않더라도 maxDiameter 변수에는 그 당시에 가장 긴 길이의 직경을 담게 된다. 

 

7. 그림으로 그려보면?

 

 Example 1. 일반 케이스

일반 케이스 때는, maxDiameter가 잘 쌓인다.

 

 Example2. 최악 케이스

최악의 케이스에서는 루트 노드를 거치지 않는다.

문제 : https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/529/week-2/3293/

Account Login - LeetCode

해설 좋은 영상 : https://www.youtube.com/watch?v=dfQseSMICV4