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

u7up0aaq  于 2023-04-19  发布在  Java
关注(0)|答案(2)|浏览(226)

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

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

它应该表示以下二叉树:

3
   /   \
  6     2
 /     /
9    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.  
  }
}
zzzyeukh

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);
}
8gsdolmq

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**获取一个数组,将其转换为树,对该树的leftright子树求和,然后报告哪个更大

这里最重要的是makeTree,它只适用于平衡二叉树,但由于这似乎是问题所指定的,所以应该没有问题。对于-1有一点额外的处理,但基本上,我们只是使用数组中的树的表示,其中,节点i的子节点在2 * i + 12 * i + 2处找到,并使用这些值递归以找到leftright子树。我认为sumTreeslargerHalf应该足够清楚。如果不是,请添加一个评论要求更多。
如果你不喜欢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'
}

相关问题