[알고리즘] Leetcode_543_Diameter_of_Binary_Tree

Problem

Solve

• 최대깊이를 구하는 dfs 재귀 알고리즘을 활용해 지름을 구하는 문제이다.
• 처음에 지름이라고 했을 때, 너비를 말하는 건가? 그렇기엔 dfs 를 쓰나 bfs 를 쓰나 깊이, 너비를 이용해서 그래프를 탐색하는 것이다. 이진트리에서 지름이란, 루트 노드를 중심으로 왼쪽의 최대 깊이와 오른쪽의 최대깊이를 합한 값이라고 보면 된다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
  int diameter = 0;
    public int dfs(TreeNode root){
      if(root == null) return 0;

      int left = dfs(root.left);
      int right = dfs(root.right);

      diameter = Math.max(diameter, left+right);

      return 1 + Math.max(left, right);
    }
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null) return 0;
        dfs(root);
        return diameter;
    }
}

• 최종적으로 반환할 값인 diameter 를 전역변수로 설정해주고, 재귀 dfs 함수에서는 각각의 높이를 반환하나 diameter 를 현재노드의 좌 우의 높이를 더한값과 diameter 를 비교하여 큰 값으로 갱신해준다.
• 예제 1에서 보면 root 1 을 시작으로 left인 2-4-5를 거쳐 다시 2에서는 좌우 높이 1과 1을 더한 값인 diameter 는 2가되고 그 값을 가지고 root 1의 right인 3은 높이가 자기 자신이므로 diameter 는 그대로 2를 가지고 height 는 1을 반환한다. 최종적인 root에서는 left 가 2 right 는 1이므로 diameter는 left+right=3을 반환한다.