vlambda博客
学习文章列表

/** * 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} */
// 横向坐标x, 纵向坐标y (均从0开始)const isValidX = function(x){ return x!=null && x!=undefined;};// 大数运算版本：Math.min, Math.maxconst minBigInt = (...args) => args.reduce((prev, curr) =>  prev < curr ? prev : curr);const maxBigInt = (...args) => args.reduce((prev, curr) =>  prev > curr ? prev : curr);// 获取 第y层节点的 最小及最大横坐标const getMinMax = function(y_dict, y){ return [y_dict[y]["min"], y_dict[y]["max"]];};// 更新 第y层节点的 最小及最大横坐标const setMinMax = function(y_dict, y, value){ let [x_min, x_max] = getMinMax(y_dict, y); y_dict[y]["min"] = isValidX(x_min)?minBigInt(value, x_min):value; y_dict[y]["max"] = isValidX(x_max)?maxBigInt(value, x_max):value;};// 递归式前序遍历二叉树，记录节点横、纵坐标const compute_X = function(node, x, y, y_dict){ if(!node){ return; } y_dict[y] = y_dict[y]?y_dict[y]:{}; setMinMax(y_dict, y, x); compute_X(node.left, x*2n, y+1, y_dict); compute_X(node.right, x*2n+1n, y+1, y_dict);};// 主函数var widthOfBinaryTree = function(root) { // 空树 if(!root){ return 0;    } // 构建辅助对象y_dict，以纵坐标(y)为key // 以最小、最大横坐标(x)组成的对象{"min":xxx, "max":xxx}为value  let y_dict = {};    let max_width = 1; // 递归式前序遍历二叉树，记录节点横、纵坐标 // 其中横坐标采用 BigInt 数据类型    compute_X(root, 0n, 0, y_dict); // 遍历y_dict，找出最小、最大横坐标之间差值最大的层 for(layer in y_dict){ let [x_min, x_max] = getMinMax(y_dict, layer); max_width = maxBigInt(max_width, x_max-x_min+1n); } // 返回该层的宽度 return max_width;}