July LeetCoding Challenge - 9

suntlee·2020년 7월 13일
0

Leetcode challenge

목록 보기
9/9

Day 9

Maximum Width of Binary Tree

문제

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

Example 1:

Input:

       1
     /   \
    3     2
   / \     \  
  5   3     9 

Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).
Example 2:

Input:

      1
     /  
    3    
   / \       
  5   3     

Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).
Example 3:

Input:

      1
     / \
    3   2 
   /        
  5      

Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).
Example 4:

Input:

      1
     / \
    3   2
   /     \  
  5       9 
 /         \
6           7

Output: 8
Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).

Note: Answer will in the range of 32-bit signed integer.

답(Java)

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        List<Integer> leftMost = new ArrayList<Integer>();
        return dfs(root, 1, 0, leftMost);
    }
    
    private int dfs(TreeNode node, Integer idx, Integer depth, List<Integer> leftMost) {
        if (node == null) return 0;
        if (depth >= leftMost.size()) leftMost.add(idx);
        int cur = idx - leftMost.get(depth) + 1;
        int left = dfs(node.left, idx * 2, depth+1, leftMost);
        int right = dfs(node.right, idx*2+1, depth+1, leftMost);
        return Math.max(cur, Math.max(left, right));
    }
}

이진트리의 너비를 구하는 알고리즘이다. 노드마다 순서대로 인덱스를 매긴 다음에 트리의 너비가 가장 클 때의 크기를 구한다. 트리의 너비란 한 레벨에서 가장 오른쪽 노드와 가장 왼쪽 노드의 차이다. 이 알고리즘에서는 각 깊이마다 가장 왼쪽 노드를 구하고 각 노드마다 너비를 구해 가장 큰 너비를 계산한다.

profile
코딩물개

관심 있을 만한 포스트

0개의 댓글