브러시 39 - 두 갈래 나무의 직경 (버클)

71. 두 갈래 나무의 직경

제목 링크 출처: 리코드(LeetCode) 링크:https://leetcode-cn.com/problems/diameter-of-binary-tree
제목 묘사는 두 갈래 나무를 정하는데, 너는 그것의 직경 길이를 계산해야 한다.두 갈래 나무의 지름 길이는 두 개의 결점 경로 길이 중 최대값입니다.이 경로는 루트 끝점을 통과할 수 있습니다.
예: 두 갈래 트리 지정하기
1/2 3/\4 5는 3을 반환합니다. 길이는 경로 [4, 2, 1, 3] 또는 [5, 2, 1, 3]입니다.
참고: 두 결점 사이의 경로 길이는 둘 사이의 모서리 수로 표시됩니다.
핵심 기술 DFS 귀속법
제목 분석

나무의 지름 = 왼쪽 나무 깊이 + 오른쪽 나무 깊이;

node를 거치면 좌우 나무의 최대 깊이의 합+1(이차 나무의 뿌리 노드 깊이는 0)

DFS를 사용하여 모든 노드의 최대 지름을 찾아내고 최대값res를 꺼냅니다.

귀속 함수 depth(node)를 정의하고 depth 함수를 호출하여 루트를 루트로 하는 두 갈래 나무의 최대 깊이를 찾아낸다

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function(root) {
    let res = 0;
    function depth(node) {
        if (!node) {
            return 0;
        }
        let left = depth(node.left);
        let right = depth(node.right);
        res = Math.max(res, left + right);
        return Math.max(left, right) + 1;
    }
    depth(root);   
    return res;
};