首页 > 代码库 > 59、剑指offer--按之字形顺序打印二叉树

59、剑指offer--按之字形顺序打印二叉树

题目描述
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
 
解题思路:通过分析,使用栈进行存储结点
打印1时,将结点2 3 放入栈中,打印3时,将3的左右孩子67分别放入栈中想放入7 再放6.
通过举例分析,对于父结点在偶数行,先放入右子结点、再放入左子结点(栈2),对于父结点在奇数行,先放入左子结点再放入右子结点(栈1)。因此使用两个栈进行存储。
使用两个栈的原因,例如2 3 都在栈中,弹出3,需要将其子结点入栈,如果只有一个栈入栈,则之后会先弹出3的子结点,再弹出2,因此,一层存入一个栈中。
 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };
10 */
11 class Solution {
12 public:
13     vector<vector<int> > Print(TreeNode* pRoot) {
14         vector<vector<int> > result;
15         vector<int> temp;//每一行的间接变量
16         if(pRoot == NULL)
17             return result;
18         stack<TreeNode *> levels[2];//0存奇数行,1存偶数行
19         int current = 0;
20         int next = 1;
21         levels[current].push(pRoot);
22         while(!levels[0].empty() || !levels[1].empty())
23         {
24             TreeNode *pNode = levels[current].top();
25             levels[current].pop();
26             temp.push_back(pNode->val);
27             if(current == 0)//奇数行,先存左子结点,再存右子结点
28             {
29                 if(pNode->left != NULL)
30                     levels[next].push(pNode->left);
31                 if(pNode->right != NULL)
32                     levels[next].push(pNode->right);
33             }
34             else//偶数行,先存右子结点,再存左子结点
35             {
36                 if(pNode->right != NULL)
37                     levels[next].push(pNode->right);
38                 if(pNode->left != NULL)
39                     levels[next].push(pNode->left);
40             }
41             if(levels[current].empty())//换行
42             {
43                 result.push_back(temp);
44                 temp.clear();//每行存入完记得清空
45                 current = 1 - current;
46                 next = 1- next;
47             }
48         }
49         return result;  
50     }
51 };

 

59、剑指offer--按之字形顺序打印二叉树