[leetcode] Diameter of Binary Tree

spark805·2021년 10월 16일
0

leetcode

목록 보기
8/9

주어진 이진 트리에서 두 노드 간 가장 긴 경로의 길이를 찾는 문제이다.
먼젓번 ListNode 때처럼 TreeNode의 class 정의가 주석에 달려있었다.
왼쪽으로 가장 긴 경로와, 오른쪽으로 가장 긴 경로를 찾아 리턴하는 형태로 문제를 풀었다.

/**
 * 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 longest;
    public int diameterOfBinaryTree(TreeNode root) {
        longest = 0;
        
        getLongest(root);
        
        return longest;
        
    }
    
    public int getLongest(TreeNode node) {
        if(node==null) {
            return 0;
        }
        int left = getLongest(node.left);
        int right = getLongest(node.right);
        
        longest = Math.max(longest, left+right);
        
        return Math.max(left, right) +1;
    }
}
profile
성장 지향 백엔드 개발자

0개의 댓글