一、前言
本系列文章为《剑指Offer》刷题笔记。
刷题平台：牛客网
书籍下载：共享资源
二、题目
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
1、思路
按之字顺序打印上图二叉树，打印顺序为：
1
3 2
4 5 6 7
15 14 13 12 12 10 9 8
为了达到这样打印的效果，我们需要使用两个栈。我们在打印某一行结点时，把下一层的子结点保存到相应的栈里。如果当前打印的是奇数层（第一层、第三层等），则先保存左子树结点再保存右子树结点到第一个栈里。如果当前打印的是偶数层（第二层、第四层等），则则先保存右子树结点再保存左子树结点到第二个栈里。
详细步骤，如上图所示。
2、代码
C++：
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 | /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: vector<vector<int> > Print(TreeNode* pRoot) { vector<vector<int> > result; if(pRoot == NULL){ return result; } stack<TreeNode* > s[2]; s[0].push(pRoot); while(!s[0].empty() || !s[1].empty()){ vector<int> v[2]; // 偶数行 while(!s[0].empty()){ v[0].push_back(s[0].top()->val); if(s[0].top()->left != NULL){ s[1].push(s[0].top()->left); } if(s[0].top()->right != NULL){ s[1].push(s[0].top()->right); } s[0].pop(); } if(!v[0].empty()){ result.push_back(v[0]); } // 奇数行 while(!s[1].empty()){ v[1].push_back(s[1].top()->val); if(s[1].top()->right != NULL){ s[0].push(s[1].top()->right); } if(s[1].top()->left != NULL){ s[0].push(s[1].top()->left); } s[1].pop(); } if(!v[1].empty()){ result.push_back(v[1]); } } return result; } }; |
Python：
感谢@小小毛提供python代码及本地测试用例。
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 | # -*- coding:utf-8 -*- class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: """docstring for Solution""" def Print(self, pRoot): resultArray = [] if not pRoot: return resultArray curLayerNodes = [pRoot] isEvenLayer = True while curLayerNodes: curLayerValues = [] nextLayerNodes = [] isEvenLayer = not isEvenLayer for node in curLayerNodes: curLayerValues.append(node.val) if node.left: nextLayerNodes.append(node.left) if node.right: nextLayerNodes.append(node.right) curLayerNodes = nextLayerNodes resultArray.append(curLayerValues[::-1]) if isEvenLayer else resultArray.append(curLayerValues) return resultArray if __name__ == '__main__': A1 = TreeNode(1) A2 = TreeNode(2) A3 = TreeNode(3) A4 = TreeNode(4) A5 = TreeNode(5) A6 = TreeNode(6) A7 = TreeNode(7) A1.left=A2 A1.right=A3 A2.left=A4 A2.right=A5 A3.left=A6 A3.right=A7 solution = Solution() ans=solution.Print(A1) print(ans) |
更多内容请访问：IT源点
注意：本文归作者所有，未经作者允许，不得转载
