Постановка задачи
Учитывая корень бинарного дерева, вернуть порядок обхода значений его узлов. (то есть слева направо, уровень за уровнем).
Постановка задачи взята с: https://leetcode.com/problems/binary-tree-level-order-traversal
Пример 1:
Input: root = [3, 9, 20, null, null, 15, 7]
Output: [[3], [9, 20], [15, 7]]
Пример 2:
Input: root = [1]
Output: [[1]]
Пример 3:
Input: root = []
Output: []
Ограничения:
- The number of nodes in the tree is in the range [0, 2000]
- -1000 <= Node.val <= 1000
Объяснение
Рекурсивная функция
С деревьями рекурсия является наиболее широко используемым подходом, поскольку код легко читается. Но для некоторых задач рекурсия увеличивает временную сложность. Для больших деревьев рекурсия может привести к переполнению стека или из-за сложности времени O(N^2) займет много времени.
Для этой задачи мы можем использовать рекурсию, но нам нужно вычислить высоту дерева.
Небольшой фрагмент описанного выше подхода на C++ будет выглядеть следующим образом:
void printLevelOrder(node* root){
int h = height(root);
for (int i = 0; i < h; i++)
printCurrentLevel(root, i);
}
void printLevel(node* root, int level){
if (root == NULL)
return;
if (level == 0)
cout << root->data << " ";
else if (level > 0) {
printLevel(root->left, level - 1);
printLevel(root->right, level - 1);
}
}
Временная сложность описанного выше подхода составляет O(N^2) для перекошенных деревьев. Наихудшая пространственная сложность составляет O(N).
Итеративный подход
Мы можем улучшить временную сложность, используя очередь в качестве структуры данных. Проверим алгоритм.
- initialize 2D array as vector vector<vector<int>> result - initialize size and i
- return result if root == null
- initialize queue<TreeNode*> q - push root to queue : q.push(root)
- initialize TreeNode* node for iterating on the tree
- loop while( !q.empty() ) // queue is not empty - initialize vector<int> tmp - set size = q.size()
- loop for i = 0; i < size; i++ - set node = q.front()
- if node->left - push in queue: q.push(node->left)
- if node->right - push in queue: q.push(node->right)
- remove the front node: q.pop()
- push the tmp to result: result.push_back(tmp)
- return result
С++ решение
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; int size, i;
if(root == NULL) return result;
queue<TreeNode*> q; q.push(root);
TreeNode* node;
while(!q.empty()){ vector<int> tmp; size = q.size();
for(i = 0; i < size; i++){ node = q.front(); if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
q.pop(); tmp.push_back(node->val); }
result.push_back(tmp); }
return result; } };
Голанг решение
func levelOrder(root *TreeNode) [][]int { result := [][]int{}
queue := []*TreeNode{root}
for len(queue) != 0 { tmp := []int{} size := len(queue)
for i := 0; i < size; i++ { if queue[0] != nil { tmp = append(tmp, queue[0].Val) queue = append(queue, queue[0].Left) queue = append(queue, queue[0].Right) }
queue = queue[1:] }
result = append(result, tmp) }
return result[:len(result)-1] }
Javascript-решение
var levelOrder = function(root) { let result = []; let queue = [];
if(root) queue.push(root);
while(queue.length > 0) { tmp = []; let len = queue.length;
for (let i = 0; i< len; i++) { let node = queue.shift(); tmp.push(node.val);
if(node.left) { queue.push(node.left); }
if(node.right) { queue.push(node.right); } }
result.push(tmp); }
return result; };
Давайте запустим наш алгоритм в пробном режиме, чтобы увидеть, как работает решение.
Input: root = [3, 9, 20, null, null, 15, 7]
Step 1: vector<vector<int>> result; int size, i;
Step 2: root == null [3, 9..] == null false
Step 3: queue<TreeNode*> q; q.push(root);
q = [3]
Step 4: loop !q.empty() q = [3] q.empty() = false !false = true
vector<int> tmp size = q.size() = 1
for(i = 0; i < 1; i++) - 0 < 1 - true
node = q.front() node = 3
if node->left - node->left = 9 - q.push(node->left) - q = [3, 9]
if node->right - node->right = 20 - q.push(node->right) - q = [3, 9, 20]
q.pop() q = [9, 20]
tmp.push_back(node->val) tmp.push_back(3)
i++ i = 1
for(i < 1) 1 < 1 false
result.push_back(tmp) result = [[3]]
Step 5: loop !q.empty() q = [9, 20] q.empty() = false !false = true
vector<int> tmp size = q.size() = 2
for(i = 0; i < 2; i++) - 0 < 2 - true
node = q.front() node = 9
if node->left - node->left = nil - false
if node->right - node->right = nil - false
q.pop() q = [20]
tmp.push_back(node->val) tmp.push_back(9)
i++ i = 1
for(i < 2) - 1 < 2 - true
node = q.front() node = 20
if node->left - node->left = 15 - q.push(node->left) - q = [20, 15]
if node->right - node->left = 7 - q.push(node->right) - q = [20, 15, 7]
q.pop() q = [15, 7]
tmp.push_back(node->val) tmp.push_back(20) tmp = [9, 20]
i++ i = 2
for(i < 2) - 2 < 2 - false
result.push_back(tmp) result = [[3], [9, 20]]
Step 6: loop !q.empty() q = [15, 7] q.empty() = false !false = true
vector<int> tmp size = q.size() = 2
for(i = 0; i < 2; i++) - 0 < 2 - true
node = q.front() node = 15
if node->left - node->left = nil - false
if node->right - node->right = nil - false
q.pop() q = [7]
tmp.push_back(node->val) tmp.push_back(15)
i++ i = 1
for(i < 2) - 1 < 2 - true
node = q.front() node = 7
if node->left - node->left = nil - false
if node->right - node->right = nil - false
q.pop() q = []
tmp.push_back(node->val) tmp.push_back(7) tmp = [15, 7]
i++ i = 2
for(i < 2) - 2 < 2 - false
result.push_back(tmp) result = [[3], [9, 20], [15, 7]]
Step 7: loop !q.empty() q = [] q.empty() = true !true = false
Step 8: return result
So we return the result as [[3], [9, 20], [15, 7]].
Первоначально опубликовано на https://alkeshghorpade.me.