我需要复习一下遍历树的知识。
我要开始面试了，技术面试官喜欢出二叉树的问题。这是 Hired.com 的一道练习题。 （我不敢在 actual 面试问题上问这个问题——这是纯粹的研究。但它难倒了我，我知道它不应该这样。）
这是一个示例问题：
给定一个用数组表示的二叉树，（其中不存在 -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.
}
}
给定一个表示为数组的二叉树
这有点不明确——数组可以通过多种方式表示二叉树。然而，习惯上分层进行，即广度优先遍历。所以
array[0]array[1]array[2]array[3]array[4]array[1]我会解决特定的任务
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);
}
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'
}
i + 1 和 2i + 2.
另请注意，列表末尾的任何额外 -1 都将被删除。所以列表的最后一个元素可能是某个节点的左孩子。我发现的最简单的解决方案是保留一个我们正在等待读取其子节点的节点队列。当我们创建新节点时，我们将它们添加到队列的末尾。 [如果这是生产代码，我会使用 Deque，但为简单起见，我使用列表。]当我们用完列表末尾时，StopIteration 终止循环。
困难的部分是建造树。其他解决方案展示了如何对左侧、右侧求和，并确定哪个更大。
@dataclass
class Node:
value: int
left: 'Node' = None,
right: 'Node' = None,
def list_to_tree(list):
if not list:
# Return whatever you're supposed to return for an empty list
return None
iterator = iter(list)
root = Node(value=next(iterator))
queue = [root]
try:
while True:
item = queue.pop(0)
value = next(iterator)
if value != -1:
item.left = Node(value=value)
queue.append(item.left)
value = next(iterator)
if value != -1:
item.right = Node(value=value)
queue.append(item.right)
except StopIteration:
return root
请注意，有稍微复杂但更快的解决方案。您不必构建树。您可以保留一个队列，显示要读取的下一个值是属于树的左侧还是右侧。单次遍历数组即可获得左和和右和，而无需实际构建树。