javascript - 二叉树的字符串表示，找到离树根最远的地方

Question

这是前阵子给我的一个算法，让我做一个测试，我想不通。有什么想法吗？

给定二叉树的递归符号:树的每个节点表示为一组三个元素:

1. 节点的值
2. 左子树
3. 右子树

因此，一棵树可以写成(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].

Answer 1

可能不是最复杂的解决方案，但它确实有效..

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();