если вход представляет собой массив, где null
означает отсутствие узла.
Вход:
[1, 2, 3, null, 5, null, 7]
Предположим, что я уже проверил ввод.
Для каждого array[i]
его родители array[i / 2]
не будут null
(рекурсивно, поэтому root не может быть null
).
Как построить дерево с такой логической связью:
1
/ \
2 3
\ \
5 7
каждый узел должен быть представлен объектом TreeNode
:
class TreeNode {
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
Я нашел здесь блог, где полное дерево был построен
но если дерево неполное, как упоминалось выше, как это сделать аккуратно и эффективно?
Данные испытаний:
[входной массив]
[-64,12,18,-4,-53,null,76,null,-51,null,null,-93,3,null,-31,47,null,3,53,-81,33,4,null,-51,-44,-60,11,null,null,null,null,78,null,-35,-64,26,-81,-31,27,60,74,null,null,8,-38,47,12,-24,null,-59,-49,-11,-51,67,null,null,null,null,null,null,null,-67,null,-37,-19,10,-55,72,null,null,null,-70,17,-4,null,null,null,null,null,null,null,3,80,44,-88,-91,null,48,-90,-30,null,null,90,-34,37,null,null,73,-38,-31,-85,-31,-96,null,null,-18,67,34,72,null,-17,-77,null,56,-65,-88,-53,null,null,null,-33,86,null,81,-42,null,null,98,-40,70,-26,24,null,null,null,null,92,72,-27,null,null,null,null,null,null,-67,null,null,null,null,null,null,null,-54,-66,-36,null,-72,null,null,43,null,null,null,-92,-1,-98,null,null,null,null,null,null,null,39,-84,null,null,null,null,null,null,null,null,null,null,null,null,null,-93,null,null,null,98]
array[i]
его родителиarray[i / 2]
не будутnull
(рекурсивно, поэтому корень не должен бытьnull
). - person Shihao Xu   schedule 22.06.2016