DepthFirstSearch 문제이다. 가장 긴 길이는 다 둘러 봐야 알수 있다.
leetcode에는 root 파라미터로 그림에 나온 트리 객체를 전달해준다. 다만 난 그걸 모르고 트리까지 해야 되는 줄 알았지만, 그래서 다시 짜보려 한다.

DFS고 Inorder search 형태로 풀어보려 한다. bottomUp 형태의 순회이고, 두 노드상 height의 길이가 가장 긴곳이 답이 된다.

leetcode에서 트리문제를 처음 접해서 당황했는데 그 이유가 input에 대한 설명 이해를 못했다.

아래처럼 root가 제공되어 지고 윗 사진에는 root = [1,2,3,4,5] 라길래 숫자 배열 주어지니 알아서 트리 만들라는줄 알았는데 또 주석땜에 고민했다가 만들다가 고치다가 이랬다. 트리 노드가 주어지는게 아니라 난 이런식으로 트리를 만들라고 생각했는데.. 초보자를 위해 파라미터에 이런 형식의 노드가 들어간다 좀 친절하게 적어줬으면 좋았을텐데 아쉽다.

어쨋건 난 js언어로 트리를 직접 만들었다. 왜냐면 vscode에 디버거 메뉴가 있는데 그걸로 run하면 call stack까지 다 보여줘서 재귀 형식의 함수는 이해하기가 쉬워진다. (안그럼 노트에 하나하나 그려가면서 해도 좋다.)

풀이

난 못풀었고 해당 플랫폼에 베댓을 갖고 왔다.
https://leetcode.com/problems/diameter-of-binary-tree/discuss/101148/Intuitive-Javascript-Solution

출력 결과는 3이다. #16행 부터 #27행 까지는 트리를 생성하는 코드로 내가 짰다(다른분의 도움과 합쳐서..)
간단하게 소개하면 js로 class를 많이 해보진 않았는데 Node라는 class 생성후 java처럼 내부 변수 정의하고 constructor 만들어서 초기화 시켜주면 틀이 잡힌다. 그럼 인스턴스 생성을 하는데 new 예약어를 통해 트리에 구조에 맞게 데이터를 넣어주면 된다.

본격적으로 문제는 결국 #36 dfs()함수를 잘 정의해주고 재귀 방식으로 돌려주는 것이다.

#37행의 return 조건은 꼭 잘 달아줘야 재귀가 무한루프에 안빠짐.

우선 #39#40행 처럼 재귀함수로 호출하면 전체 노드에서 left node 끝까지 갔다가, leaf node에서 자식이 없으니 #39,#40 에 cosnt left,right 값이 #37행의 !node return 0; 조건에 의해 0을 각각 할당 받을 것이다.

즉 트리 모양이 위와 같으니, 앞서 말한 leaf node 4번 노드까지 가서 dfs 함수 내에서 #39,#40행에 각 변수에 0을 리턴 받는다.
그리고 지름을 생각해보면 결국 부모 노드 밑에 자식 노드 left와 right의 합중 가장 큰게 지름이 되는 원리다.
그러니 dfs()는 모든 노드를 도니깐, #44행처럼 Math.max(diameter, left + right) 를 정의해주면 모든 노드를 돌면서 left자식노드, right자식노드의 합 중 최대값을 찾게 되고 그걸 전역변수에 넣어서 가장 바깥 함수에 return 부분에 입력해주면 지름을 구하게 된다.

그리고 앞에 설명한 #39, #40행에서 dfs() 함수 내부에서 node 파라미터가 있을떄, 즉 자식이 있을때 return 조건을 정의해줘야 하는데, 자식이 있다는 말은 적어도 노드와 노드사이 간선(=edge)가 1개는 있다는 말이니까 return 에 1+ 를 기본적으로 적어주고, left,right 자식노드 중 큰 값 +1을 return 해서 부모 노드 dfs() 블록 범위서 사용할수 있게 해주면 된다.
그러면 트리의 지름이 나오게 된다.