Постановка на проблема
Като се има предвид root на двоично дърво, върнете обхождането на ниво отдолу нагоре на стойностите на неговите възли. (т.е. отляво надясно, ниво по ниво от листа до корена).
Изявлението на проблема е взето от: https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
Пример 1:
Input: root = [3, 9, 20, null, null, 15, 7] Output: [[15, 7], [9, 20], [3]]
Пример 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
Обяснение
Изложението на проблема е подобно на старата ни публикация в блога „LeetCode Binary Tree Level Order Traversal“. Вместо да отпечатваме нивата ред по ред отгоре надолу, трябва да ги отпечатаме в обратен ред.
Рекурсивна функция
Можем да модифицираме рекурсивното решение на LeetCode Binary Tree Level Order Traversal, за да отпечатаме нивото на дървото отдолу нагоре.
C++ фрагмент от решението ще бъде както по-долу.
void reverseLevelOrder(node* root) {
int h = height(root);
int i;
for(i = h; i >= 1; i--)
printGivenLevel(root, i);
}
void printGivenLevel(node* root, int level) {
if (root == NULL)
return;
if (level == 1)
cout << root->data << ' ';
else if (level > 1)
{
printGivenLevel(root->left, level - 1);
printGivenLevel(root->right, level - 1);
}
}
int height(node* node) {
if (node == NULL)
return 0;
else
{
int lheight = height(node->left);
int rheight = height(node->right);
if (lheight > rheight)
return(lheight + 1);
else return(rheight + 1);
}
}
Времевата сложност на горния подход е O(n^2), а пространствената сложност е O(n).
Опашки: итеративно решение
Можем да намалим времевата сложност до 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 node->val to tmp. tmp.push_back(node->val)
- push the tmp to result: result.push_back(tmp)
- loop while end
- reverse result
- return result
Времевата сложност на горния подход е O(n), а пространствената сложност е O(n).
Нека проверим нашия алгоритъм в C++, Golang и Javascript.
C++ решение
class Solution {
public:
vector<vector<int>> levelOrderBottom(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);
}
reverse(result.begin(), result.end());
return result;
}
};
Разтвор на Golang
func levelOrderBottom(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)
}
result = reverse(result)
return result[1:]
}
func reverse(input [][]int) [][]int {
var output [][]int
for i := len(input) - 1; i >= 0; i-- {
output = append(output, input[i])
}
return output
}
Javascript решение
var levelOrderBottom = 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.reverse();
};
Нека изпробваме нашия алгоритъм, за да видим как работи решението.
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: reverse(result.begin(), result.end())
Step 9: return result
So we return the result as [[15, 7], [9, 20], [3]].
