二叉树的宽度
层序遍历,超时了。
/**
* 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;
let max = 0;
const queue = [root];
while(queue.length) {
let n = queue.length;
max = Math.max(max, n);
for(let i = 0; i < n; i++) {
const node = queue.shift();
queue.push(node ? node.left : null);
queue.push(node ? node.right : null);
}
while(queue.length && !queue[queue.length - 1]) queue.pop();
while(queue.length && !queue[0]) queue.shift();
}
return max;
};
由于题目约束,答案在32位有符号整数的表示范围内。js用这些方法的时候会越界,可以采用办法剪枝,保证pos不越界。
剪枝方法:当当前层数只有一层的时候,pos重置到0
var widthOfBinaryTree = function(root) {
if (!root) return 0;
const queue = [[root, 0]];
let width = 0;
while (queue.length) {
const len = queue.length;
if (len === 1) {
queue[0][1] = 0;
}
let left = Infinity;
let right = -Infinity;
for (let i = 0; i < len; i++) {
const [node, index] = queue.shift();
left = Math.min(index, left);
right = Math.max(index, right);
if (node.left) {
queue.push([node.left, 2 * index]);
}
if (node.right) {
queue.push([node.right, 2 * index + 1]);
}
}
width = Math.max(width, right - left + 1);
}
return width;
};
- Runtime: 142 ms, faster than 12.26%
- Memory Usage: 43.1 MB, less than 94.19%
/**
* 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;
const queue = [[root, 0]];
let width = 0;
while (queue.length) {
const len = queue.length;
if (len === 1) {
queue[0][1] = 0;
}
let left = Infinity;
let right = -Infinity;
for (let i = 0; i < len; i++) {
const [node, index] = queue.shift();
left = Math.min(index, left);
right = Math.max(index, right);
if (node.left) {
queue.push([node.left, 2 * index]);
}
if (node.right) {
queue.push([node.right, 2 * index + 1]);
}
}
width = Math.max(width, right - left + 1);
}
return width;
};
网友评论