如何使用JavaScript将数组转换为二叉树？

u7up0aaq 于 2023-04-19 发布在 Java

关注(0)|答案(2)|浏览(227)

我需要复习一下穿越树木的知识。
我马上就要开始面试了，科技面试官们喜欢给予二叉树问题。这是Hired.com网站上的一个练习题。（如果是真正的面试问题，我可不敢提这个问题--这是纯粹的学习。但它难倒了我，我知道它不应该这样。）
下面是一个示例问题：
给定一个二叉树，表示为一个数组，（其中节点-1是不存在的）写一个函数，确定树的左分支或右分支是否更大。每个分支的大小是节点值的总和。如果左侧较大，则函数应返回“Left”，如果右侧较大，则返回“Right”。
这里有个问题。他们给出的示例数组是：

[3, 6, 2, 9, -1, 10]

它应该表示以下二叉树：

我只是不知道如何基本上把这个数组变成二叉树。我想我可以创建一个二叉树就好了，但我不知道如何创建一个树 * 从 * 这样的数组。这是那些事情之一，我“曾经知道”，但只是为我的生活不能弄清楚。
下面是我使用的代码（Javascript）;

// went with a class, know I could probably do this FP, but f'it.
class TreeNode {
  constructor(value){
    this.value = value;
    this.left = null;
    this.right = null;
  }
  setLeft(node){
    this.left = node;
  }
  setRight(node){
    this.right = node;
  }
}

const buildNode = (root, valLeft, valRight){
  if(valLeft > 0){
    root.setLeft(new TreeNode(valLeft));
  }
  if(valRight > 0){}
    root.setRight(new TreeNode(valRight));
  }
  return root;
}

const solution = (arr) => {
  const rootNode = buildNode(new Node(arr.shift()), arr.shift(), arr.shift());
  /* this is where I run into trouble */
  if(arr.length){
    buildNode(rootNode.left, arr.shift(), arr.shift());
    buildNode(rootNode.right, arr.shift(), arr.shift());
    // I know I have to make a recursive function here,
    // and just can't wrap my head around it.  
  }
}

JavaScript

来源：https://stackoverflow.com/questions/76047836/how-can-i-convert-an-array-to-a-binary-tree-with-javascript

2条答案

按热度按时间

zzzyeukh1#

给定一个表示为数组的二叉树
这是一个有点不明确的-有很多方法可以表示一个数组二叉树。然而，习惯上是分层的，即从广度优先遍历。所以array[0]是第零层的根，array[1]和array[2]是第一层的子节点，array[3]和array[4]是array[1]的第二级上的子级，以此类推。
这种表示的好处是，你可以通过将节点索引除以2来轻松地得到父节点，并通过将节点索引乘以2来得到子节点（根据你的计数方式，还可以考虑off-by-one错误）。
我会解决这个特殊的任务

function solution(arr) {
  function getNode(index) {
    if (index >= arr.length || arr[index] == -1) return null;
    const node = new Node(arr[index]);
    node.setLeft(getNode((index+1)*2-1));
    node.setRight(getNode((index+1)*2));
    return node;
  }
  return getNode(0);
}

赞(0）回复(0）举报 2023-04-19

8gsdolmq2#

我发现一个更简单的FP版本：

const makeTree = (nodes, i = 0) =>
  i >= nodes .length 
    ? null
    : {
        value: nodes [i] == -1 ? null : nodes [i], 
        left: makeTree (nodes, 2 * i + 1), 
        right: makeTree (nodes, 2 * i + 2)
      }

const sumTree = (node) => node == null 
  ? 0 
  : (node .value || 0) + sumTree (node .left) + sumTree (node .right)

const largerHalf = (
  nodes = [], 
  tree = makeTree (nodes), 
  lSum = sumTree (tree .left), 
  rSum = sumTree (tree .right)
) => lSum > rSum ? 'Left' : rSum > lSum ? 'Right' : 'Equal'

const nodes = [3, 6, 2, 9, -1, 10]

console .log (largerHalf (nodes)) //=> 'Left'

***makeTree**递归地将数组转换为树格式，如

{
     value: 3,
     left: {
         value: 6,
         left: {value: 9, left: null, right: null},
         right: {value: -1, left: null, right: null}
     },
     right: {
         value: 2,
         left: {value: 10, left: null, right: null},
         right: null
     }
}

***sumTree**递归累加树中的值
***largerHalf**获取一个数组，将其转换为树，对该树的left和right子树求和，然后报告哪个更大

这里最重要的是makeTree，它只适用于平衡二叉树，但由于这似乎是问题所指定的，所以应该没有问题。对于-1有一点额外的处理，但基本上，我们只是使用数组中的树的表示，其中，节点i的子节点在2 * i + 1和2 * i + 2处找到，并使用这些值递归以找到left和right子树。我认为sumTrees和largerHalf应该足够清楚。如果不是，请添加一个评论要求更多。
如果你不喜欢largerHalf中的额外参数（有一些很好的理由不喜欢），那么我们可以引入一个快速的call函数，并像这样写：

const call = (fn, ...args) => fn (...args)

const largerHalf = (nodes = []) => call (( 
  tree = makeTree (nodes), 
  lSum = sumTree (tree .left), 
  rSum = sumTree (tree .right)
) => lSum > rSum ? 'Left' : rSum > lSum ? 'Right' : 'Equal')

或者写一个更强制的版本，像这样：

const largerHalf = (nodes = []) => { 
  const tree = makeTree (nodes)
  const lSum = sumTree (tree .left)
  const rSum = sumTree (tree .right)
  return lSum > rSum ? 'Left' : rSum > lSum ? 'Right' : 'Equal'
}

赞(0）回复(0）举报 2023-04-19

我来回答

如何使用JavaScript将数组转换为二叉树？

2条答案

相关问题

热门标签

最新问答