[LeetCode] 543 Diameter of Binary Tree JavaScript

문제 링크

Diameter of Binary Tree - LeetCode

 

문제 유형

트리, 백트래킹

 

문제 풀이

이번 문제는 트리의 지름을 구하는 문제이다. 여기서 지름(diameter)는 트리의 어떤 두 노드 사이의 가장 긴 경로의 길이를 말한다. 해당 문제는 백트래킹을 적용하여 각 노드를 post-order 순회한다. 이를 통해 각 노드의 left depth와 right depth를 구한다. 저장된 지름보다 left depth와 right depth를 합한 현재 노드의 지름이 더 크면 최대 지름을 갱신한다. 현재 노드의 최대 depth는 left depth와 right depth 중 큰 값에 1을 더한 것이 된다. 따라서 트리의 노드 개수가 n개일 때, 시간복잡도는 O(n)을 갖는다.

 

코드

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

 

참고

https://www.youtube.com/watch?v=1VNWJTbE2pM