这些小活动你都参加了吗?快来围观一下吧!>>
电子产品世界 » 论坛首页 » 嵌入式开发 » STM32 » binary-tree-zigzag-level-order-traversal

共2条 1/1 1 跳转至

binary-tree-zigzag-level-order-traversal

高工
2018-01-19 17:52:07     打赏

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).

For example:
Given binary tree{3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7


return its zigzag level order traversal as:

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


confused what"{1,#,2,3}"means? > read more on how binary tree is serialized on OJ.


OJ's Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

   1
  / \
 2   3
    /
   4
    \
     5
The above binary tree is serialized as"{1,2,3,#,#,4,#,#,5}".题意:Z字形打印二叉树思路:层次遍历二叉树。对于偶数层在进行逆转就行;[cpp] view plain copy
  1. class Solution {  

  2. public:  

  3.     vector<vector<int>> zigzagLevelOrder(TreeNode* root)  

  4.     {  

  5.         vector<vector<int>> res;  

  6.         if (root==NULL)  

  7.         {  

  8.             return res;  

  9.         }  

  10.   

  11.         queue<TreeNode*> q;  

  12.         q.push(root);  

  13.   

  14.         while (q.size())  

  15.         {  

  16.             vector<int> level;  

  17.             for (int i=0, n=q.size(); i<n; i++)  

  18.             {  

  19.                 TreeNode* tmp = q.front();  

  20.                 q.pop();  

  21.   

  22.                 level.push_back(tmp);  

  23.                 if (tmp->left)  

  24.                 {  

  25.                     q.push(tmp->left);  

  26.                 }  

  27.                 if (tmp->right)  

  28.                 {  

  29.                     q.push(tmp->right);  

  30.                 }  

  31.             }  

  32.             res.push_back(level);  

  33.         }  

  34.   

  35.         for (int i=0; i<res.size(); i++)  

  36.         {  

  37.             if ((i+1)%2==0)  

  38.             {  

  39.                 reverse(res[i].begin(), res[i].end());  

  40.             }  

  41.         }  

  42.   

  43.         return res;  

  44.     }  

  45. };  




管理员
2018-01-22 09:45:08     打赏
2楼

谢谢楼主分享


共2条 1/1 1 跳转至

回复

匿名不能发帖!请先 [ 登陆 注册 ]