103.md

Binary Tree Zigzag Level Order Traversal

题目

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

example:

Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
   
return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]

思路

对树采用先根遍历。使用一个二维数组vector<vector> result存放结果。使用一个int level来表示当前层的层数

对于遍历的每一个结点，如果该结点是该层的第一个结点，则在result中的加入一个新的vector用来存放改层的结点。

如果不是该当前层的第一个结点，则根据level来判断，当前层是右到左还是左到右。level%2==0表示为0,2,4···不需要在 result中倒过来存放， 所以直接在对应层result[level] 后面push_back即可。如果level%2!=0表示1,3,5则在对应成result[level]的最前面push_back当前结点元素。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        trverse(result,0,root);
        return result;
    }
    
    void trverse(vector<vector<int>> &result,int level,TreeNode *node){
        if(!node) return;
        //是当前层最新的结点
        if(level>=result.size()){
            result.emplace_back(vector<int>{node->val});
        }else if(level%2==0){
            //表示在不需要倒过来存放的层数
            result[level].emplace_back(node->val);
        }else{
            //需要倒过来存放
            result[level].insert(result[level].begin(),node->val);
        }
        trverse(result,level+1,node->left);
        trverse(result,level+1,node->right);
    }
};