如何在 TypeScript 中输出 Hackerrank 二叉树问题？

Question

这是 Hackerrank 问题：

给定一个指向二叉树根的指针，你需要打印这棵树的层序遍历。在层序遍历中，从左到右逐层访问节点。完成函数并在单行中打印由 space.

分隔的值

我已经定义了函数 levelOrder()。但是不知道如何标准输出。还有为什么这里没有给出Node class。当我为这个问题检查 Java 等其他语言时，我看到声明了 Node class 。他们怎么能期望我把字符串当作节点来充当呢？我很困惑。

这是 hackerrank 编辑器中的完整代码，包括它们的设置：

'use strict';

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString: string = '';
let inputLines: string[] = [];
let currentLine: number = 0;
process.stdin.on('data', function(inputStdin: string): void {
    inputString += inputStdin;
});

process.stdin.on('end', function(): void {
    inputLines = inputString.split('\n');
    inputString = '';
    main();
});

function readLine(): string {
    return inputLines[currentLine++];
}

function main() {
    // Enter your code here
    
    function levelOrder(root: any): string {
        const queue = [root];
        let visited = "";
        let currentNode = root;
        while (queue.length > 0) {
            currentNode = queue.shift();
            visited += `${currentNode.val} `;
            if (currentNode.left) queue.push(currentNode.left);
            if (currentNode.right) queue.push(currentNode.right);
        }
        return visited;
    }
    // How I am going to invoke my function and stdout return val here?
}

Answer 1

你是对的，这令人困惑。

显然，HackerRank 并没有真正在代码挑战的 TypeScript 版本上付出太多努力，因为模板代码中没有规定将文本输入转换为 TreeNode 数据结构，就像完成的那样对于其他语言。

其次，挑战也没有解释基于文本的输入是如何组织的。为此，我查看了 HackerRank 上的其他一些二叉树挑战，发现对于 this one，输入格式是描述的：

The first line contains an integer , the number of nodes in the tree. Next line contains space separated integer where th integer denotes node[i].data.

Note: Node values are inserted into a binary search tree before a reference to the tree's root node is passed to your function. In a binary search tree, all nodes on the left branch of a node are less than the node value. All values on the right branch are greater than the node value.

所以，二叉树其实就是一棵二叉搜索树！并且应按顺序将输入值插入其中，以最终构建作为挑战主题的树。

出于某种神秘的原因，在使用 TypeScript 而不是其他语言解决挑战时，您必须自己执行此操作。

关于输出的问题，可以直接使用console.log.

以下是一些通用代码，可用于使用 TypeScript 解决 HackerRank 上的二叉树问题：

class TreeNode {
    left: TreeNode;
    right: TreeNode;
    data: number;
    
    constructor(value: number) {
        this.data = value;
        this.left = null;
        this.right = null;
    }
}

function insertNode(node: TreeNode, data: number): TreeNode {
    if (node === null) return new TreeNode(data);
    if (data < node.data) {
        node.left = insertNode(node.left, data);
    } else {
        node.right = insertNode(node.right, data);
    }
    return node;
}

function inputTree(): TreeNode {
    const nodeValues = inputLines[1].match(/\d+/g).map(Number);
    let root: TreeNode = null;
    for (const nodeValue of nodeValues) {
        root = insertNode(root, nodeValue);
    }
    return root;
}

有了这个，你的 main 代码可以有这样的结构：

function main() {
    const root = inputTree();
    const result = /* your solution code here, producing an array */;
    console.log(result.join(" "));
}

为了完成我的回答，我在这里提供了一个剧透，说明我将如何为这个特定的代码挑战编写解决方案的核心，但我想上面的内容你真的已经足够了：

function* levelOrder(root: TreeNode) { const queue: TreeNode[] = [root]; for (let i = 0; i < queue.length; i++) { const node = queue[i]; yield node.data; if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } } function main() { const root = inputTree(); const result = [...levelOrder(root)]; console.log(result.join(" ")); }

如何在 TypeScript 中输出 Hackerrank 二叉树问题？

How to stdout Hackerrank Binary Tree question in TypeScript?

binary-tree

node.js

typescript