二叉树的字符串表示法，找到距离树根最远的地方
问题描述：
这是一个算法，我刚才给出了一个测试，我无法弄清楚。有任何想法吗？二叉树的字符串表示法，找到距离树根最远的地方
您将得到的二进制树的递归符号：一个树的每个节点被表示为一组三个元素：节点
- 值
因此，一棵树可以写为(value left_subtree right_subtree)。
如果节点不存在，则表示为空集：()。
您的任务是从左到右的顺序获取离树根最远的节点列表。
在一个节点的表示法中，它的值和子树由一个空格字符分隔。
例子：
// 2
// /\
// / \
// / \
// / \
// / \
// 7 5
// /\ \
// / \ \
// 2 6 9
// /\ /
// / \ /
// 5 11 4
tree = "(2 (7 (2()()) (6 (5()()) (11()()))) (5() (9 (4()())())))"
treeBottom(tree) // Desired output: [5, 11, 4].
答
的事实，这不是一个[标签
也许不是最先进的解决方案，但它的工作原理..
var tree = "(2 (7 (2()()) (6 (5()()) (11()()))) (5() (9 (4()())())))";
var level = 0;
var rootLeafs = []
var leaf = -1;
var i;
var parseToken = {
"(": enterLevel,
")": leaveLevel,
" ": separate,
}
function isValidTreeElement() {
applyFn = parseToken[tree[i]]||parseNumber;
return applyFn()
}
function enterLevel() {
if (i > 0 && tree[i-1] != " ") {
alert("Nodes must be separated by space");
return false;
}
level++;
// entering new root leaf
if (level == 2) {
leaf++;
rootLeafs[leaf] = [];
}
return true;
}
function leaveLevel() {
level--;
return true;
}
function separate() {
if (i > 0 && tree[i-1] == " ") {
alert("Multiple spaces in row");
return false;
}
return true;
}
function parseNumber() {
var advance = tree.substring(i).indexOf(" ");
if (advance < 1) {
alert("Number must followed by space");
return false;
}
var num = Number(tree.substring(i,i+advance));
if (isNaN(num)) {
alert("Expected number, given: " + tree.substring(i,i+advance));
return false;
}
i += advance - 1; // move index to last char of number
// add value to current leaf level
if (level > 1) {
try {
rootLeafs[leaf][level-2].push(num);
} catch(e) {
rootLeafs[leaf][level-2] = [num];
}
}
return true;
}
function walk() {
for (i = 0; i < tree.length; i++) {
if (!isValidTreeElement()) {
return;
}
}
// get last level from each root leaf
var results = rootLeafs.reduce(function(a, b) {
return a.concat(b.slice(-1)[0]);
}, []);
console.log('Result: ' + results);
}
walk();
再说：二进制搜索树]，到目前为止你尝试过什么，你卡在哪里？你可以在你的问题中包含你的代码吗？ – Marco
括号的每个级别离根都是另一步。因此，最深嵌套层次的非空节点（或多个节点）距离根节点最远。因此，如果您要跟踪当前的嵌套级别以及当前最深的节点，则可以在字符串的单次扫描中执行此操作。 –