重构C函数以查找O(n)中二进制树的直径到JavaScript
Refactoring C function to find diameter of Binary Tree in O(n) to JavaScript
我很难理解/重写这里给出的用于查找二叉树直径的"优化"C函数。我不明白它是如何记录高度的。我知道它使用了第二个参数height来实现这一点,但在代码中我甚至没有看到使用了height参数。我很难理解C语言中的函数,我主要用JavaScript编写。我能够重写页面上的所有其他函数,尽管没有问题。
/*The second parameter is to store the height of tree.
Initially, we need to pass a pointer to a location with value
as 0. So, function should be used as follows:
int height = 0;
struct node *root = SomeFunctionToMakeTree();
int diameter = diameterOpt(root, &height); */
int diameterOpt(struct node *root, int* height)
{
/* lh --> Height of left subtree
rh --> Height of right subtree */
int lh = 0, rh = 0;
/* ldiameter --> diameter of left subtree
rdiameter --> Diameter of right subtree */
int ldiameter = 0, rdiameter = 0;
if(root == NULL)
{
*height = 0;
return 0; /* diameter is also 0 */
}
/* Get the heights of left and right subtrees in lh and rh
And store the returned values in ldiameter and ldiameter */
ldiameter = diameterOpt(root->left, &lh);
rdiameter = diameterOpt(root->right, &rh);
/* Height of current node is max of heights of left and
right subtrees plus 1*/
*height = max(lh, rh) + 1;
return max(lh + rh + 1, max(ldiameter, rdiameter));
}
通过引用传递的近似等价物(在您提供的示例中也有注释)将是属性为的对象
var heightHolder = { height:0};
var diam = diameterOpt(root, heightHolder);
console.log(heightHolder.height);
function diameterOpt(root, heightHolder){
if (!root) {
heightHolder.height = 0;
return 0;
}
var refLh = {height:0};
var refRh = {height:0};
var ldiameter = diameterOpt(root.left, refLh);
....
heightHolder.height = Math.max(refLh.height, refRh.height) + 1;
return ...
}
通常情况下,你不会走JavaScript支持以更自然的方式返回多个值这样疯狂的路线:
function diameterOpt(root){
if (!root){
return {height:0, diameter:0};
}
var leftResult = diameterOpt(root.left);
var rightResult = diameterOpt(root.right);
return {
height: Math.max(leftResult.height,rightResult.height) + 1;
diameter:
Math.max(leftResult.height+rightResult.height + 1,
Math.max(leftResult.diameter, rightResult.diameter))
}
}
相关文章:
- Javascript 二进制搜索/插入预处理
- 如何在JavaScript中实现二进制搜索
- 如何在Windows中将Javascript文件编译成二进制文件
- 如何使用JavaScript粘贴原始二进制文件而不出现“无效字符”错误
- Javascript-将类型化数组保存为blob,并作为二进制数据读回
- Javascript:相当于PHP'使用RAW二进制输出的s hash_hmac.()
- 使用JavaScript从二进制文件中读取字节,而不使用jQuery
- javascript二进制操作don'不适用于选项
- 获取二进制数据并将其保存为.mp3文件Javascript
- 必须对 JavaScript 进行哪些更改才能使其可编译为二进制
- 将 DD/MMM/YYYY 转换为二进制/纪元日期 JavaScript
- 将用JavaScript生成的二进制文件保存到iPad
- 如何使用JavaScript在Internet Explorer中将文件(DOCX或XLSX或PNG)读取为二进制流
- 如何将二进制数据映射到javascript中的字符
- Javascript-如何快速构建不同正整数数组的二进制表示
- 如何通过JavaScript将二进制(输入)转换为字符串(输出)
- 十进制到二进制代码Javascript
- 如何在不编码或保存数据的情况下将二进制数据从javascript传递到actionscript(网页到flash)
- 有没有更有效的方法在 JavaScript 中执行二进制插入排序
- 如何在 JavaScript ajax 调用中从 PHP 传递中获取二进制数据