Блог

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

Например: данное двоичное дерево {3,9,20,#,#,15,7},

         3 
       /  
      9   20 
     /  
   15   7 
  

верните его обход порядка на уровне зигзага как:

 [   
    [3],
    [20,9],
    [15,7]
]
  

---

Лично я думаю,
Временная сложность = O (n * высота), n — количество узлов, height — высота данного двоичного дерева.

    getHeight()             => O(n) 
   traverseSpecificLevel() => O(n)
   reverseVector()         => O(n)
   swap()                  => O(1)
  

---

C

 /**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        vector<vector<int>> list;

        // Input validation.
        if (root == NULL) return list;

        // Get the height of the binary tree.
        int height = getHeight(root);

        bool left_to_right = true;
        for (int level = 0; level <= height; level   ) {
            vector<int> subList;
            traverseSpecificLevel(root, level, subList);

            if (left_to_right == true) {
                // Add subList into list.
                list.push_back(subList);
                // Update left_to_right flag.
                left_to_right = false;

            } else {
                // Reverse subList.
                reverseVector(subList);
                // Add reversed subList into list.
                list.push_back(subList);
                // Update left_to_right flag.
                left_to_right = true;
            }
        }
        return list;
    }

    int getHeight(TreeNode *root) {
        // Base case.
        if (root == NULL || (root->left == NULL amp;amp; root->right == NULL)) return 0;
        else return 1   max(getHeight(root->left), getHeight(root->right));
    }

    void traverseSpecificLevel(TreeNode *root, int level, vector<int> amp;subList) {
        // Base case.
        if (root == NULL) return;
        if (level == 0) {
            subList.push_back(root->val);
            return;
        }

        // Do recursion.
        traverseSpecificLevel(root->left, level - 1, subList);
        traverseSpecificLevel(root->right, level - 1, subList);
    }

    void reverseVector(vector<int> amp;list) {
        // Input validation.
        if (list.size() <= 1) return;

        int start = 0;
        int end = list.size() - 1;
        while (start < end) {
            swap(list, start, end);

            start   ;
            end --;
        }
    }

    void swap(vector<int> amp;list, int first, int second) {
        int tmp = list[first];
        list[first] = list[second];
        list[second] = tmp;
    }
};
  

Вы можете сделать это за линейное время. Создайте вектор > результат размером max_height. Рекурсивный обход дерева с сохранением уровня узла. Для каждого узла возвращайте его значение к результату [level]. Чем просто обратный результат [1], результат [3], … .

Кстати, есть swap(x,y) функция и reverse(a.begin(), a.end()) function (где a — вектор), вы можете использовать их вместо того, чтобы реализовывать их самостоятельно. Включите algorithm для этого.