Постановка задачи
Учитывая root
двоичного дерева, представьте, что вы стоите на правой стороне от него, верните значения видимых узлов, упорядоченные сверху вниз.
Постановка задачи взята с: https://leetcode.com/problems/binary-tree-right-side-view
Пример 1:
Input: root = [1, 2, 3, null, 5, null, 4] Output: [1, 3, 4]
Пример 2:
Input: root = [1, null, 3] Output: [1, 3]
Пример 3:
Input: root = [] Output: []
Ограничения:
- The number of nodes in the tree is in the range [0, 100]. - -100 <= Node.val <= 100
Объяснение
Проблема может быть решена с помощью обхода по порядку или обхода по порядку уровней. Давайте рассмотрим обход порядка уровней с помощью очередей.
Обход порядка уровней
Мы исследовали обход порядка уровней с использованием как рекурсивного, так и итеративного подхода в нашем предыдущем сообщении в блоге LeetCode — обход порядка двоичного дерева.
Давайте воспользуемся итеративным подходом и сначала проверим алгоритм.
- if root == NULL - return {} - initialize queue<TreeNode*> q push root q.push(root) - initialize vector<int> result int queueSize, i - loop while !q.empty() - set queueSize = q.size() - loop for i = queueSize; i > 0; i-- - set node = q.front() - q.pop() - if i == queueSize - result.push_back(node->val) - if node->right != NULL - q.push(node->right) - if node->left != NULL - q.push(node->left) - end for loop - end while loop - return result
Временная сложность описанного выше подхода составляет O(n), а пространственная сложность — O(n).
Давайте проверим наш алгоритм на C++, Golang и Javascript.
С++ решение
class Solution { public: vector<int> rightSideView(TreeNode* root) { if(root == NULL) { return {}; } queue<TreeNode*> q; q.push(root); vector<int> result; int queueSize, i; while(!q.empty()) { queueSize = q.size(); for(i = queueSize; i > 0; i--) { TreeNode* node = q.front(); q.pop(); if(i == queueSize) { result.push_back(node->val); } if(node->right != NULL) { q.push(node->right); } if(node->left != NULL) { q.push(node->left); } } } return result; } };
Голанг решение
func rightSideView(root *TreeNode) []int { if root == nil { return []int{} } queue := []*TreeNode{root} result := []int{} queueSize, i := 0, 0 var node *TreeNode for len(queue) != 0 { queueSize = len(queue) for i = queueSize; i > 0; i-- { node = queue[0] queue = queue[1:] if i == queueSize { result = append(result, node.Val) } if node.Right != nil { queue = append(queue, node.Right) } if node.Left != nil { queue = append(queue, node.Left) } } } return result }
Javascript-решение
var rightSideView = function(root) { if(root == null) { return []; } let queue = [root]; let result = []; let queueSize = 0, i = 0; let node; while(queue.length > 0 ) { queueSize = queue.length; for(i = queueSize; i > 0; i--) { node = queue.shift(); if(i == queueSize) { result.push(node.val); } if(node.right != null) { queue.push(node.right); } if(node.left != null) { queue.push(node.left); } } } return result; };
Давайте запустим наш алгоритм в пробном режиме, чтобы увидеть, как работает решение.
Input: root = [1, 2, 3, null, 5, null, 4] Step 1: if root == NULL root -> 1 false Step 2: queue<TreeNode*> q q.push(root) q = [1] Step 3: vector<int> result int queueSize, i Step 4: loop while(!q.empty()) !q.empty() = true queueSize = q.size() = 1 loop for i = queueSize; i > 0; i-- i = 1 1 > 0 true node = q.front() = ->1 q.pop() q = [] if i == queueSize 1 == 1 true result.push_back(q->val) result.push_back(1) result = [1] if node->right != NULL node->right = ->3 true q.push(node->right) q.push(->3) q = [3] if node->left != NULL node->left = ->2 true q.push(node->right) q.push(->2) q = [3, 2] i-- i = 0 for i > 0 0 > 0 false Step 5: loop while(!q.empty()) !q.empty() = true queueSize = q.size() = 2 loop for i = queueSize; i > 0; i-- i = 2 2 > 0 true node = q.front() = ->3 q.pop() q = [2] if i == queueSize 2 == 2 true result.push_back(q->val) result.push_back(3) result = [1, 3] if node->right != NULL node->right = ->4 true q.push(node->right) q.push(->4) q = [2, 4] if node->left != NULL NULL != NULL false i-- i = 1 loop for i > 0 1 > 0 true node = q.front() = ->2 q.pop() q = [4] if i == queueSize 1 == 2 false if node->right != NULL node->right = ->5 true q.push(node->right) q.push(->5) q = [4, 5] if node->left != NULL NULL != NULL false i-- i = 0 loop for i > 0 0 > 0 false Step 6: loop while(!q.empty()) !q.empty() = true queueSize = q.size() = 2 loop for i = queueSize; i > 0; i-- i = 2 2 > 0 true node = q.front() = ->4 q.pop() q = [5] if i == queueSize 2 == 2 true result.push_back(q->val) result.push_back(4) result = [1, 3, 4] if node->right != NULL NULL != NULL false if node->left != NULL NULL != NULL false i-- i = 1 loop for i > 0 1 > 0 true node = q.front() = ->5 q.pop() q = [] if i == queueSize 1 == 2 false if node->right != NULL NULL != NULL false if node->left != NULL NULL != NULL false i-- i = 0 loop for i > 0 0 > 0 false Step 7: loop while(!q.empty()) !q.empty() = false q = [] Step 8: return result We return the answer as [1, 3, 4].
Первоначально опубликовано на https://alkeshghorpade.me.