我需要复习一下穿越树木的知识。
我马上就要开始面试了,科技面试官们喜欢给予二叉树问题。这是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.
}
}
2条答案
按热度按时间zzzyeukh1#
给定一个表示为数组的二叉树
这是一个有点不明确的-有很多方法可以表示一个数组二叉树。然而,习惯上是分层的,即从广度优先遍历。所以
array[0]
是第零层的根,array[1]
和array[2]
是第一层的子节点,array[3]
和array[4]
是array[1]
的第二级上的子级,以此类推。这种表示的好处是,你可以通过将节点索引除以2来轻松地得到父节点,并通过将节点索引乘以2来得到子节点(根据你的计数方式,还可以考虑off-by-one错误)。
我会解决这个特殊的任务
8gsdolmq2#
我发现一个更简单的FP版本:
***
makeTree
**递归地将数组转换为树格式,如***
sumTree
**递归累加树中的值***
largerHalf
**获取一个数组,将其转换为树,对该树的left
和right
子树求和,然后报告哪个更大这里最重要的是
makeTree
,它只适用于平衡二叉树,但由于这似乎是问题所指定的,所以应该没有问题。对于-1
有一点额外的处理,但基本上,我们只是使用数组中的树的表示,其中,节点i
的子节点在2 * i + 1
和2 * i + 2
处找到,并使用这些值递归以找到left
和right
子树。我认为sumTrees
和largerHalf
应该足够清楚。如果不是,请添加一个评论要求更多。如果你不喜欢
largerHalf
中的额外参数(有一些很好的理由不喜欢),那么我们可以引入一个快速的call
函数,并像这样写:或者写一个更强制的版本,像这样: