题干
662. Maximum Width of Binary Tree
Difficulty: Medium
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.
给予一个二叉树，得到这个树的最大宽度。
最大宽度指的是二叉树的同一层中，最左边的非空节点和最右边的非空节点之间的距离。
解题思路
如同题干中分析的，只需要找到每一层最左边的节点和最右边的节点就可以了，中间所有的节点我们都不care。
不过说来惭愧，这道中等难度的题，解了两个小时，写了三种写法，其中第一种是错的，第两种都谈不上最优解，而如果一个认真学数据结构的人来做这题的话，可能第一次就能写出最优解了。
第一种错误写法：
var widthOfBinaryTree = function (root) {
let left = [];
let right = [];
if (!root) {
return 0
}
const traverse = (root) => {
if (root.left) {
left.push(0);
traverse(root.left);
} else if (root.right) {
left.push(1);
traverse(root.right)
}
};
const inversiveTraverse = (root) => {
if (root.right) {
right.push(0);
inversiveTraverse(root.right);
} else if (root.left) {
right.push(1);
inversiveTraverse(root.left)
}
};
traverse(root);
inversiveTraverse(root);
left.map((x, i, arr) => {
if (i) {
return arr[i - 1] * 2 + x;
} else {
return x;
}
});
right.map((x, i, arr) => {
if (i) {
return arr[i - 1] * 2 + x;
} else {
return x;
}
});
let max = -1;
left.forEach((x, i) => {
let tmp = (2 ** (i + 1) - left[i] - right[i]);
if (tmp > max) {
max = tmp;
}
})
return max;
};
其实思路上没有太大的问题，遍历每个层级上最靠左和最靠右的节点即可，之所以这么想是因为我觉得没有必要遍历所有的节点，尽可能的遍历两边的节点就可以了，然后通过记录走过的路径来计算出最靠边的节点的位置，进而计算出最大的宽度，然而这个写法的问题在于我没法处理某个不在最后一层的叶子节点，进而我想到了一个改进写法，DP。
动态规划：
如果在遍历的时候走到了某个不处于最后一层的叶子节点，为了遍历到更深的层级，我需要回溯到父节点，然而一般二叉树是不会有父节点指针的，所以我需要额外维护两个队列，记录遍历时走过的路径，以及走过的方向。
var widthOfBinaryTreeDP = function (root) {
if (!root) {
return 0;
}
// 计算所处的位置
const calcPos = (arr) => {
let sum = 0;
arr.forEach((x) => {
sum = sum * 2 + x;
});
return sum;
}
let left = []; // 记录每一层最左边的节点
let leftNode = []; // 遍历时的节点路径队列
let leftDirection = []; // 遍历时的路径方向队列
const leftDp = (root) => {
if (!root) return;
if (root.left) {
// 记录路径的节点和方向
leftNode.push(root);
leftDirection.push(0);
// 第一个找到的节点必定是最远的那个，记录距离
if (left[leftNode.length - 1] === undefined) {
left.push(calcPos(leftDirection));
}
leftDp(root.left);
} else if (root.right) {
leftNode.push(root);
leftDirection.push(1);
if (left[leftNode.length - 1] === undefined) {
left.push(calcPos(leftDirection));
}
leftDp(root.right);
} else {
// 如果找到叶子节点，则开始回溯
let node = leftNode.pop();
let direction = leftDirection.pop();
// 回溯到第一个存在右节点且在上次遍历中走向了左节点的节点
while ((direction === 1 || (direction === 0 && !node.right)) && leftNode.length) {
node = leftNode.pop();
direction = leftDirection.pop();
}
// 回溯成功，改变路径方向，改为走向右节点
if (leftNode.length || direction === 0) {
leftNode.push(node);
leftDirection.push(1);
if (left[leftNode.length - 1] === undefined) {
left.push(calcPos(leftDirection));
}
leftDp(node.right);
} else {
// 根节点再上一次遍历中已经走向了右节点，则说明已经遍历所有可能性
return;
}
}
}
// 对最右节点的遍历与上面类似，只是优先找最右节点。
let right = [];
let rightNode = [];
let rightDirection = [];
const rightDp = (root) => {
if (!root) return;
if (root.right) {
rightNode.push(root);
rightDirection.push(0);
if (right[rightNode.length - 1] === undefined) {
right.push(calcPos(rightDirection));
}
rightDp(root.right);
} else if (root.left) {
rightNode.push(root);
rightDirection.push(1);
if (right[rightNode.length - 1] === undefined) {
right.push(calcPos(rightDirection));
}
rightDp(root.left);
} else {
let node = rightNode.pop();
let direction = rightDirection.pop();
while ((direction === 1 || (direction === 0 && !node.left)) && rightNode.length) {
node = rightNode.pop();
direction = rightDirection.pop();
}
if (rightNode.length || direction === 0) {
rightNode.push(node);
rightDirection.push(1);
if (right[rightNode.length - 1] === undefined) {
right.push(calcPos(rightDirection));
}
rightDp(node.left);
} else {
return;
}
}
}
leftDp(root);
rightDp(root);
let max = 1;
// 计算最大宽度
left.forEach((x, i) => {
let tmp = (2 ** (i + 1) - left[i] - right[i]);
if (tmp > max) {
max = tmp;
}
})
return max;
};
成功AC，本来写到这就结束了，然而却看到一句Your runtime beats 5.83% of javascript submission。
这也太丢脸了，这算法我调了整整一个小时啊，不行我得写个好看的。
深度优先遍历
一开始要我用遍历的时候，我是拒绝的，毕竟我只需要最靠边的节点就可以了，没有必要去遍历那些中间的节点，但是由于我一开始并不知道深度，所以我在做DP的时候其实也把大半的节点给遍历了，但是DP我需要做两次，第一次找最左，第二次找最右，于是乎总体的时间是大于做一次遍历的。
如果我知道树的深度，那么用DP则是更好的一个解法，可惜求解树的深度的算法本身就是一个BFS，所以这题的解法最优解实际上是BFS和DFS，我自己写了一个BFS版本的。
var widthOfBinaryTreeDFS = function (root) {
let ranges = [];
let max = 0;
const traverse = (root, depth, pos) => {
if (!root) {
return;
}
if (root.left) {
left = traverse(root.left, depth + 1, pos * 2);
}
if (root.right) {
right = traverse(root.right, depth + 1, pos * 2 + 1);
}
if (ranges[depth]) {
if (pos <= ranges[depth][1] && pos > ranges[depth][1]) {
return;
} else {
if (pos > ranges[depth][1]) {
ranges[depth][1] = pos;
} else if (pos < ranges[depth][0]) {
ranges[depth][0] = pos;
}
let range = ranges[depth][1] - ranges[depth][0] + 1;
if (max < range) {
max = range;
}
}
} else {
ranges[depth] = [pos, pos];
if (max === 0) {
max = 1;
}
}
}
traverse(root, 0, 0);
return max;
};
记录下每个节点的深度和位置，再判断该节点是否比同深度其他节点要更加靠近边界，若是则更新当前深度的宽度，并和最大宽度做比较，来更新最大宽度。
写的简单，算的还快。做了一点小优化以后得出了上面的算法，成功AC，得到一句Your runtime beats 98.06 % of javascript submissions。
网友评论