Hello, everyone, I am the beaten Amumu, love algorithm front-end fish old. Recently, I will frequently share with you my thoughts and experiences in the process of brush algorithm. If you also want to improve the forced case of fish old, welcome to pay attention to me, learn together.
The title
662. Maximum width of binary tree
Given a binary tree, write a function to get the maximum width of the tree. The width of the tree is the maximum width of any layer. This binary tree has the same structure as a full binary tree, but some nodes are empty.
The width of each layer is defined as the length between two endpoints (the left-most and right-most non-empty nodes of the layer, with null nodes between the two endpoints also counted in the length).
Example 1:
Input: 1 / \ 3 2 / \ \ 5 3 9 Output: 4 Explanation: The maximum value occurs at the third layer of the tree with a width of 4 (5,3, NULL,9).Copy the codeExample 2:
Input: 1/3 / \ 5 3 Output: 2 Explanation: The maximum occurs at level 3 of the tree with a width of 2 (5,3).Copy the codeExample 3:
Input: 1 / \ 3 2/5 Output: 2 Explanation: The maximum occurs at level 2 of the tree with a width of 2 (3,2).Copy the codeExample 4:
Input: 1 / / 2/3/5 9 / \ 6 7 output: 8: maximum value appeared in tree layer 4, width of 8 (6, null, null, null, null, null, null, 7).Copy the codeNote: The answer is within the representation range of a 32-bit signed integer.
Train of thought
- All nodes in each layer can remove the Null portion before and after each node until it has a value, and then determine the maximum length of the valid portion.
- According to this idea, my first thought is to use an array to store the values of each round, and then use a method to remove the left and right empty Spaces. In this way, the length of the values obtained in each round can be judged by taking the maximum length of the previous round and the maximum length of the current round.
Violent solution
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
* @return {number}* /
var widthOfBinaryTree = function(root) {
let maxCount = 0;
// Record the list data of the previous round
let prevArr = [ root ];
while (filterRightNullData(prevArr).length) {
maxCount = Math.max(maxCount, filterRightNullData(prevArr).length);
prevArr = prevArr.reduce((total, cur) = > {
total.push(cur && cur.left);
total.push(cur && cur.right);
returntotal; } []); }return maxCount;
};
// Delete the Null elements on both sides
function filterRightNullData(arr) {
while (arr.length && arr[0= = =null) {
arr.shift();
}
while (arr.length && arr[arr.length - 1= = =null) {
arr.pop();
}
return arr;
}
Copy the codeTipping site
The truth is, brute force doesn’t work, we’re out of memory, so we need to find a pattern. We can count only the valid nodes. We also need to add a coordinate value to the valid node and record its number. In this way, we can achieve the desired effect by subtracting the coordinate value of the left and right valid nodes.
Flip over the code again
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
* @return {number}* /
var widthOfBinaryTree = function(root) {
if(! root)return 0;
// Record the list data of the previous round
let prevArr = [ { node: root, index: 0}];// Record the maximum length
let maxCount = 1;
while (prevArr.length) {
// If there are more than two nodes to determine the index difference, remember that + 1 is required between the difference and the number
if (prevArr.length > 1) {
let curCount = prevArr[prevArr.length - 1].index - prevArr[0].index + 1;
maxCount = Math.max(maxCount, curCount);
}
prevArr = prevArr.reduce((total, cur) = > {
// Only non-empty nodes are stored
// The left node equals 2n, and the right node equals 2n + 1
cur.node.left && total.push({ node: cur.node.left, index: cur.index * 2 });
cur.node.right && total.push({ node: cur.node.right, index: cur.index * 2 + 1 });
returntotal; } []); }return maxCount;
};
Copy the codeThe scene of the accident
why
As stated in the problem, the answer is within the representation range of 32-bit signed integers, which means that the result may be extremely large. We may not be able to store such large numbers with ordinary number, so we need to perform a mod operation on large numbers.
The final code
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
* @return {number}* /
var widthOfBinaryTree = function(root) {
if(! root)return 0;
// Record the list data of the previous round
let prevArr = [ { node: root, index: 0}];// Record the maximum length
let maxCount = 1;
// The number may be too large to overflow, so we need to do the mod operation
let mod = Math.pow(2.32);
while (prevArr.length) {
// If there are more than two nodes to determine the index difference, remember that + 1 is required between the difference and the number
if (prevArr.length > 1) {
let curCount = prevArr[prevArr.length - 1].index - prevArr[0].index + 1;
maxCount = Math.max(maxCount, curCount);
}
prevArr = prevArr.reduce((total, cur) = > {
// Only non-empty nodes are stored
// the left node is equal to 2n, the right node is equal to 2n + 1, the number may be too large to be mod
const curIndex = cur.index * 2 % mod;
cur.node.left && total.push({ node: cur.node.left, index: curIndex });
cur.node.right && total.push({ node: cur.node.right, index: curIndex + 1 });
returntotal; } []); }return maxCount;
};
Copy the codeIf you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.