LeetCode (662) - Maximum Width of Binary Tree

하단 Title 클릭 시 해당 문제 페이지로 이동합니다.

- Maximum Width of Binary Tree

• Acceptance: 39.7%
• Difficulty: Medium

문제 설명

Given the root of a binary tree, return the maximum width of the given tree.

The maximum width of a tree is the maximum width among all levels.

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

It is guaranteed that the answer will in the range of 32-bit signed integer.

Constraints:

• The number of nodes in the tree is in the range [1, 3000].
• -100 <= Node.val <= 100

예시 1

Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).

예시 2

Input: root = [1,3,null,5,3]
Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).

예시 3

Input: root = [1,3,2,5]
Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).

문제 풀이

• 단순히 해당 depth의 노드의 갯수로만 width를 정하는것이 아닌 null인 노드가 존재하더라도 가장 바깥 노드(end-node) 기준으로 width를 정해야 한다.

• BFS를 이용해 문제를 해결

• Queue에 주어진 TreeNode 와 depth, 해당 depth에서 몇번째 순서인지를 나타내는 cnt를 묶어 Node 클래스로 만들었다.

• Queue의 로직은 다음과 같다.

1. queue에 꺼낸 node의 depth와 curDepth를 비교해 다르다면, 다음 depth로 넘어간것이기 때문에 결과값을 max 값으로 갱신한다. 또한 curDepth를 갱신하고 left 값도 갱신한다.
2. right 값을 계속 cnt로 변경하여 가장 큰 right값을 구한다.
3. 해당 node의 자식이 있다면 queue에 넣는다. 이때 가장 중요한 점은 cnt를 계산할 때, left라면 자식 node의 cnt는 부모 node의 cnt * 2, right라면 cnt * 2 + 1로 처리하는것.

코드

import java.util.LinkedList;
import java.util.Queue;

/**
 * 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 {
    private class Node{
        TreeNode treeNode;
        int depth;
        int cnt;

        public Node(TreeNode treeNode, int depth, int cnt) {
            this.treeNode = treeNode;
            this.depth = depth;
            this.cnt = cnt;
        }
    }

    public int widthOfBinaryTree(TreeNode root) {
        int result = 0;
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(root, 0, 0));

        int curDepth = 0, left = 0, right = 0;
        while (!queue.isEmpty()) {
            Node node = queue.poll();

            if (node.depth != curDepth) {
                result = Math.max(result, right - left + 1);
                curDepth = node.depth;
                left = node.cnt;
            }

            right = node.cnt;

            if (node.treeNode.left != null) {
                queue.add(new Node(node.treeNode.left, node.depth + 1, node.cnt * 2));
            }

            if (node.treeNode.right != null) {
                queue.add(new Node(node.treeNode.right, node.depth + 1, node.cnt * 2 + 1));
            }
        }
        return Math.max(result, right - left + 1);
    }
}