题目描述

image.png

image.png

题解

这里并不按层去遍历，而是用先序遍历构造出所需的vector结果

• 使用递归算法，从上往下传递一遍。每当第一次到新的一层，需要在结果后面追加一个新的vector
• 在递归单元中，先根节点再左子树然后右子树，这样每一层中左边的元素一定比右边的元素先访问
• 为了形成之字形，递归函数带上层数这一参数，偶数层从该层vector的后面插入元素，奇数层从该层vector的前面插入元素

代码

// zigzagLevelOrder.cpp
#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x): val(x), left(NULL), right(NULL){}
    ~TreeNode(){
        if (this->left != NULL){
            delete this->left;
            this->left = NULL;
        }
        if (this->right != NULL){
            delete this->right;
            this->right = NULL;
        }
    }
};

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > zigzagLevelOrder(TreeNode* root) {
        // write code here
        if (root != NULL){
            zigzagLevelOrder(root, 0);
        }
        return result;

    }
private:
    vector<vector<int>> result;
    void zigzagLevelOrder(TreeNode* root, int layer){
        if (result.size() <= layer){
            vector<int> layerVector;
            layerVector.push_back(root->val);
            result.push_back(layerVector);
        }
        else{
            if (layer % 2 == 0){
                result[layer].push_back(root->val);
                
            }
            else{
                result[layer].insert(result[layer].begin(), root->val);
            }
        }
        if (root->left != NULL){
            zigzagLevelOrder(root->left, layer + 1);
        }

        if (root->right != NULL){
            zigzagLevelOrder(root->right, layer + 1);
        }
    }
};

int main(){
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->left->left = new TreeNode(15);
    root->left->right= new TreeNode(7);
    Solution s;
    vector<vector<int>> result = s.zigzagLevelOrder(root);
    for (int i = 0; i < result.size(); i++){
        for (int j = 0; j < result[i].size(); j++){
            cout << result[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}