JavaScript实现的打印二进制树的左视图返回错误的结果

JavaScript implementation of printing left view of binary tree is returning incorrect result

本文关键字：视图 返回 错误 结果 实现 打印 二进制 JavaScript      更新时间：2023-09-26

我正在尝试打印一个二叉树的左视图，就像这里在geeksfoekes上看到的那样。由于某种原因，它不起作用，我怀疑这与max_level有关。结果是[ 12, 10, 30, 25, 40 ]，我期待[12,10,25]。

JS代码

var Node = function(val) {
    this.val = val;
    this.left = this.right = null;
};
var leftViewUtil = function(root, level, max, result) {
    if (root === null) return;
    if (max.level < level) {
        max.level = level;
        result.arr.push(root.val);
    }
    leftViewUtil(root.left, ++level, max, result);
    leftViewUtil(root.right, ++level, max, result);
};
var leftView = function(root) {
    var result = {
        arr: []
    };
    var max_level = {level: 0};
    leftViewUtil(root, 1, max_level, result);
    return result.arr;
};
root = new Node(12);
root.left = new Node(10);
root.right = new Node(30);
root.right.left = new Node(25);
root.right.right = new Node(40);
var run = function() {
    console.log(leftView(root));
};
run();

链接页面上的代码之间的差异是

// Recur for left and right subtrees
leftViewUtil(root->left, level+1, max_level);
leftViewUtil(root->right, level+1, max_level);

与

leftViewUtil(root.left, ++level, max, result);
leftViewUtil(root.right, ++level, max, result);

这里将level增加两次，同时应该将相同的值传递给两个递归调用。正确使用level+1，或者在调用之前进行增量：

++level;
leftViewUtil(root.left, level, max, result);
leftViewUtil(root.right, level, max, result);

使用哈希表在几行代码中找到树的左视图和右视图。

right_view(root,num, result) {
    if(root == null) {
        return 0
    }
    right_view(root.Left, num+1, result)
    right_view(root.Right, num+1, result)
    result[num] = root.Value
}
left_view(root,num, result) {
    if(root == null) {
        return 0
    }
    left_view(root.Left, num+1, result)
    left_view(root.Right, num+1, result)
    if(result[num] == undefined) {
        result[num] = root.Value
    }
}

正在调用具有根节点的函数

right_view_result = {}
right_view(root,1,right_view_result)
console.log(right_view_result)

正在调用具有根节点的函数

left_view_result = {}
left_view(root,1,left_view_result)
console.log(left_view_result)
相关文章：