Binary Tree Zigzag Level Order Traversal

Binary Tree Zigzag Level Order Traversal

Description:

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,#,#,15,7},

3
/
9 20
    /
    15 7

return its bottom-up level order traversal as:
[
    [3],
    [20,9],
    [15,7]
]

分析：

简单题，和普通的BFS没有多大区别。

思路：

  1. 当访问节点后，如果左（右）孩子不为nullptr就把左（右）孩子加入queue中（先左后右）。

  2. 当访问节点时，需要分情况讨论此节点所在的层是从左遍历还是从右边遍历，所以需要一个变量level记录当前的层数，以及一个变量node_num来记录当前层的节点数。

    • 如果从左遍历，则把节点的值通过push_back()添加到临时vector（下方代码里是变量tem）的后端。
    • 如果从右遍历，则把节点的值通过insert()插入到临时vector（下方代码里是变量tem）的首部。

注意：最后一层遍历得到的临时vector（下方代码里是变量tem）是没有添加到rs中的，因为此时queue（下方代码里是变量q）为空，最后一个else语句没有执行，所以需要在while循环后添加语句if (tem.size() > 0) rs.push_back(tem);。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
 

class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: A list of lists of integer include 
     *          the zigzag level order traversal of its nodes' values 
     */
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode *root) {
        // write your code here
        vector<vector<int> >  rs;
        if (root == nullptr) return rs;

        int level = 1;
        int curr_num = 0;
        int total_num = 1;
        int node_num = total_num - curr_num;
        
        vector<int> tem;
        queue<TreeNode *> q;
        q.push(root);

        while (!q.empty()) {
            if (node_num != 0) {
                node_num--;
                curr_num++;
                TreeNode *node = q.front();
                q.pop();

                if (level % 2 == 1) {
                    tem.push_back(node->val);
                }
                else {
                    vector<int>::iterator it = tem.begin();
                    tem.insert(it, node->val);
                }


                if (node->left != nullptr) {
                    q.push(node->left);
                    total_num++;
                }
                if (node->right != nullptr) {
                    q.push(node->right);
                    total_num++;
                }
            }
            else {
                rs.push_back(tem);
                tem.clear();

                level++;
                node_num = total_num - curr_num;
            }
        }
        
        if (tem.size() > 0) {
            rs.push_back(tem);
        }

        return rs;
    }
};