[LeetCode]이진트리의 직경(java,python)

이 문제는 “이진트리”의 직경이다.

최대길이를 갖는 path는 마치 어떤 노드를 루트로 하는 트리의 모습을 띨 것이다.

• 즉, 어떤 노드의 Left Subtree의 “maxDepth” + Right subtree의 “maxDepth” 와 같다.
• 재귀적으로 파고들어가 leaf에서부터 값을 업데이트해가야한다.

/**
 * 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 {
    public int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        
        // 어떤 노드의 left subtree의 최대 depth + right subtree의 최대 depth
        // 위에서부터 내려가면 복잡해짐 . leaft에서부터 올라가는 것을 생각한다. 
        traverse(root);
        return max;

    }
    
    public int traverse(TreeNode n){
        if( n == null)
            return 0;       
        
        int left = traverse(n.left);
        int right = traverse(n.right);
        
        // 현재 노드를 루트로 하는 path의 최대 길이 
        max = Math.max(max,left+right);
        
        // 리턴하는 값은 이 노드로부터 최대로 내려 갈 수 있는 depth
        return Math.max(left,right)+1;
        
    }
}

class Solution:
    longest: int = 0
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def dfs(node: TreeNode) -> int:
            if not node:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            
            self.longest = max(self.longest, left+right)
            return max(left,right)+1
        dfs(root)
        return self.longest