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

Question

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

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

Have the function TreeConstructor(strArr) take the array of strings stored in strArr, which will contain pairs of integers in the following format (i1, i2) where i1 represents a child a node in a tree and the second integer i2 signifies that it is the parent of i1. For example if strArr is ["(1,2)", "(2,4)", "(7,2)"]

    4 
   /
  2
 / \
1   7

which you can see forms a proper binary tree. Your program should, in this case, return the string true because a valid binary tree can be formed. If a proper binary cannot be formed with the integer pairs, then return the string false. All of the integers within the tree will be unique, which means there can only be one node in the tree with the given integer value

Examples

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 没有用于任何用途)

相反，您应该只查看输入中给出的表示边 的父子关系，并使用该信息来构建图形。最后，您应该验证该图是否表示 binary tree .想一想二叉树的显着特征是什么以及如何验证它们。

提示 1:

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

提示 2:

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

提示 3:

所有向上的路径都应该在同一个节点(根)结束

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

// 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));
}

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