lintcode二叉树的锯齿形层次遍历 (双端队列)

 

题目链接:

  http://www.lintcode.com/zh-cn/problem/binary-tree-zigzag-level-order-traversal/

二叉树的锯齿形层次遍历 

  给出一棵二叉树,返回其节点值的锯齿形层次遍历(先从左往右,下一层再从右往左,层与层之间交替进行) 

样例

  给出一棵二叉树 {3,9,20,#,#,15,7},

      3
     / \
    9  20
      /  \
     15   7

  返回其锯齿形的层次遍历为:

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

思路:

  我们用双端队列模拟一下这个过程:开始的时候是正向遍历,3通过push_front()放入队列Q, 形成Q[3]。接着我们规定正向遍历的时候从队列前端去元素,下一层元素放入队列的时候是放入队列的后端;而反向遍历的时候正好相反,唯一不同的就是反向遍历时,下一层的右孩子结点(如果有)先放入队列的前端。

  开始Q[3](从前端取数字), 然后下一层放入后是Q[9,20](从后端去数字),20的下一层放入后是Q[15,7,9], 然后变成Q[15,7](从前端去数字),最后得到遍历的结果。

代码实现:

/**
 * 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>> vv;
        if(root == NULL) return vv;
        deque<TreeNode *> q;
        q.push_back(root);
        bool dir = true;//true表示从左向右存储层次遍历,否则是从右向左
        int levelCnt = 1;//上一层的节点数目
        int curLevelCnt = 0;//下一层节点数目
        vector<int> v;
        while(!q.empty()){
            TreeNode *cur;
            if(dir){
                cur = q.front();
                q.pop_front();
            } else {
                cur = q.back();
                q.pop_back();
            }
            if(dir){
                if(cur->left){
                    q.push_back(cur->left);
                    ++curLevelCnt;
                }
                if(cur->right){
                    q.push_back(cur->right);
                    ++curLevelCnt;
                }
            } else {
                if(cur->right){
                    q.push_front(cur->right);
                    ++curLevelCnt;
                }
                if(cur->left){
                    q.push_front(cur->left);
                    ++curLevelCnt;
                }
            }
            v.push_back(cur->val);
            --levelCnt;
            if(levelCnt == 0){//这一层完毕
                vv.push_back(v);
                v.clear();
                levelCnt = curLevelCnt;
                curLevelCnt = 0;
                dir = !dir;
            }
        }
        return vv;
    }
};

 

上一篇:lintcode二叉树的锯齿形层次遍历 (双端队列)


下一篇:[LeetCode] Range Sum Query - Mutable