NC14二叉树的之字形层序遍历

NC14二叉树的之字形层序遍历

- 题目描述：

- 题目链接：
https://www.nowcoder.com/practice/47e1687126fa461e8a3aff8632aa5559?tpId=117&&tqId=34935&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking

- 设计思想：

详细操作流程看下图

- 代码：
c++版本:

 /**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > zigzagLevelOrder(TreeNode* root) {
        // write code here
        vector<vector<int> >res; //用于存储返回结果
        queue<TreeNode*> q; //创建队列用于存储节点
        if(root == NULL) return res; //当为空的时候直接返回
        int height = 1;  //用于处理之字形遍历，偶数就直接插入，偶数就插入temp头
        q.push(root); //插入节点
        while(!q.empty()){
            vector<int> temp; // 存储每一层的数字
            int n = q.size(); // 队列大小表示当前层数的元素个数
            for(int i = 0;i < n;i ++){
                TreeNode* node = q.front(); //取出队列的第一个元素
                q.pop();
                if(height % 2 == 0){
                    temp.insert(temp.begin(),node->val); // 如果层数是偶数就插入到头
                }else{
                    temp.push_back(node->val); //如果层数是奇数就直接放进去  
                }
                if(node->left != NULL) q.push(node->left);//如果左子树不为空就递归左子树
                if(node->right!= NULL) q.push(node->right);//如果右子树不为空就递归右子树

            }
            height ++; //高度++
            res.push_back(temp); //把这一层的节点插入到res中
        }
        return res;

    }
};

Java版本：

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }