Постановка задачи

Учитывая корень бинарного дерева, вернуть порядок обхода значений его узлов. (то есть слева направо, уровень за уровнем).

Постановка задачи взята с: 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.