我检查图是否为二叉树总是返回 false

Question

我有一个中等水平的问题，甚至无法思考如何解决这个问题，我的解决方案可能有点矫枉过正，因为我不知道如何遍历数组中的一堆数字来检查它是否是二叉树或不。无论如何，程序总是返回 false

如果你对这个问题有更好的答案那就完美了

让函数TreeConstructor(strArr)获取存储在 中的字符串数组strArr，该数组将包含以下格式的整数对 (i1, i2)，其中 i1 表示树中的子节点，第二个整数 i2 表示它是 i1 的父节点。例如如果strArr是["(1,2)", "(2,4)", "(7,2)"]

    4 
   /
  2
 / \
1   7

你可以看到它形成了一个正确的二叉树。在这种情况下，您的程序应该返回字符串 true，因为可以形成有效的二叉树。如果无法用整数对形成正确的二进制，则返回字符串 false。树中的所有整数都是唯一的，这意味着树中只能有一个节点具有给定的整数值

例子

input: ["(1,2)", "(2,4)", "(5,7)", "(7,2)", "(9,5)"]
output: true


input ["(1,2)", "(1,3)"]
output: false

我尝试了一下，但总是返回 false。我的代码很可能是矫枉过正。

class Node {
  // The constructor
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
  // Basic insert node
  insert(value) {
    let currentNode = this;
    while (true) {
      if (value < currentNode.value) {
        if (currentNode.left === null) {
          currentNode.left = new Node(value);
          break;
        } else {
          currentNode = currentNode.left;
        }
      } else {
        if (currentNode.right === null) {
          currentNode.right = new Node(value);
          break;
        } else {
          currentNode = currentNode.right;
        }
      }
    }
    return currentNode
  }
    // check if BST is valid or not
    isValidBST(node, min = null, max = null) {
    if (!node) return true;
    if (max !== null && node.value >= max) {
      return false;
    }
    if (min !== null && node.value <= min) {
      return false;
    }
    const leftSide = this.isValidBST(node.left, min, node.value);
    const rightSide = this.isValidBST(node.right, node.value, max);
    return leftSide && rightSide;
  }
}

// Convert the strings to a number 
function convertListToNumber(str, i) {
  return str[i].split('(').join('').split(')').join('').split(',').join('')
}

这是主要功能

function TreeConstructorTwo(strArr) { 
  // code goes here  
  startValueFromList = convertListToNumber(strArr, 0)
  // Parent Node here
  startParentNode = startValueFromList[1];
  // Child Node here
  startChildNode = startValueFromList[0];
  // Add parent Node and childNode
  node = new Node(startParentNode);
  node.insert(startChildNode);
  // Loop through the entire array
  for (i = 1; i < strArr.length; i++) {
    myListValue = convertListToNumber(strArr, i);
    console.log(myListValue.length)
    // Loop the "12" in the string and convert it to a number
    for (j = 0; j < myListValue.length; j++) {
       node.insert(myListValue[j])
    }
    parentNode = Number(myListValue[0])
  }
  // Check if the BST is valid or not
  return node.isValidBST(node)
}

// keep this function call here 
console.log(TreeConstructorTwo(["(1,2)", "(2,4)", "(5,7)", "(7,2)", "(9,5)"]));

Answer 1

您似乎误解了任务。当表示的树是二叉树（不一定是二叉搜索树）时，该函数应返回 true。

您的代码从第一个元素创建一棵树，然后采用任何下一个节点将其插入到该树中，与二分搜索属性保持一致，而不考虑输入中的对要求第一个元素是第二个元素的直接子元素。（您的变量parentNode没有用于任何用途）

相反，您应该只查看输入中给出的代表边 的子父关系，并使用该信息来构建图形。最后，您应该验证该图是否代表二叉树。思考二叉树有哪些显着特征以及如何验证它们。

提示1：

任何节点都不应该有两个父节点

提示2：

任何节点都不应该有 3 个子节点

提示3：

所有向上路径应以同一节点（根）结束

下面的剧透解决方案不会返回 true/false，而是返回一个字符串，指示树是否“ok”，或者为什么不“ok”。这对于调试更有用，并且仍然很容易转换为布尔值。

// This function returns the reason why it considers the input
// not a binary tree. "ok" otherwise.
function isBinaryTree(edgesStr) {
    const childToParent = new Map(edgesStr.map(edge => edge.match(/\d+/g)));
    // No node should have 2 parents
    if (childToParent.size < edgesStr.length) return "node with two parents";
    // No node should have 3 children
    const degree = {};
    for (const [child, parent] of childToParent) {
         if ((++degree[parent] || (degree[parent] = 1)) > 2) return "node with three children";
    }
    // All upward paths lead to the same root (no cycles)
    const nodes = {};
    let current = 0;
    let countRoots = 0;
    for (let node of childToParent.keys()) {
        current++;
        while (node && !nodes[node]) {
            nodes[node] = current;
            node = childToParent.get(node);
        }
        if (!node && countRoots++) return "disconnected";
        if (node && nodes[node] == current) return "cycle";
    }
    return "ok";
}

const tests = [
    ["(2,1)", "(3,1)", "(4,2)", "(5,2)", "(6,3)", "(7,3)"],
    ["(1,2)", "(3,2)", "(2,12)", "(5,2)"],
    ["(2,1)", "(3,1)", "(5,4)", "(5,2)"],
    ["(2,1)", "(4,3)"],
    ["(1,2)", "(3,4)", "(4,5)", "(5,3)"],
];

for (const test of tests) {
    console.log(isBinaryTree(test));
}

注意：我会用首字母小写字母来命名该函数，因为通常的做法是为类名保留首字母大写字母。