662. Maximum Width of Binary Tree

662. 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:

\ 3 2 / \ \

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

\

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

\

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

\ 3 2 / \ 5 9 / \

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.

思路： Depth-First Search Intuition and Algorithm

Traverse each node in depth-first order, keeping track of that node’s position. For each depth, the position of the first node reached of that depth will be kept in left[depth].

Then, for each node, a candidate width is pos - left[depth] + 1. We take the maximum of the candidate answers.

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { int ans; Map left; public int widthOfBinaryTree(TreeNode root) { ans = 0; left = new HashMap(); dfs(root, 0, 0); return ans; } public void dfs(TreeNode root, int depth, int pos) { if (root == null) return; left.computeIfAbsent(depth, x-> pos); ans = Math.max(ans, pos - left.get(depth) + 1); dfs(root.left, depth + 1, 2 * pos); dfs(root.right, depth + 1, 2 * pos + 1); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。