题目:
请实现一个函数按照之字形打印二叉树, 即第一行按照从左到右的顺序打印, 第二层按照从右至左的顺序打印, 第三行按照从左到右的顺序打印, 其他行以此类推.
分析:
实际上是二叉树的层次遍历, 只不过每一行输出的方向都是相反的, 每遍历二叉树的结点时, 都将其内的每一个结点的左右孩子都保存好, 设置一个标志, ture 时就正序输出, false 就逆序输出 val, 直到所有的结点都打印完即可.
程序:
- C++
- class Solution {
- public:
- vector<vector<int>> Print(TreeNode* pRoot) {
- if(pRoot == nullptr)
- return res;
- vector<TreeNode*> printS;
- vector<TreeNode*> temp;
- printS.push_back(pRoot);
- bool flag = true;
- while(!printS.empty()){
- //vector<TreeNode*> temp;
- vector<int> resTemp;
- for(auto i:printS){
- if(i->left != nullptr)
- temp.push_back(i->left);
- if(i->right != nullptr)
- temp.push_back(i->right);
- }
- if(flag){
- for(int i = 0; i <printS.size(); ++i)
- resTemp.push_back(printS[i]->val);
- }
- else{
- for(int i = printS.size()-1; i>= 0; --i)
- resTemp.push_back(printS[i]->val);
- }
- flag = !flag;
- res.push_back(resTemp);
- printS.swap(temp);
- temp.clear();
- }
- return res;
- }
- private:
- vector<vector<int>> res;
- };
- Java
- import java.util.ArrayList;
- /*
- public class TreeNode {
- int val = 0;
- TreeNode left = null;
- TreeNode right = null;
- public TreeNode(int val) {
- this.val = val;
- }
- }
- */
- public class Solution {
- public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
- if(pRoot == null)
- return res;
- ArrayList<TreeNode> printS = new ArrayList<>();
- ArrayList<TreeNode> temp = new ArrayList<>();
- boolean flag = true;
- printS.add(pRoot);
- while(!printS.isEmpty()){
- ArrayList<Integer> resTemp = new ArrayList<>();
- for(TreeNode i:printS){
- if(i.left != null)
- temp.add(i.left);
- if(i.right != null)
- temp.add(i.right);
- }
- if(flag){
- for(int i = 0; i <printS.size(); ++i)
- resTemp.add(printS.get(i).val);
- }
- else{
- for(int i = printS.size()-1; i>= 0; --i)
- resTemp.add(printS.get(i).val);
- }
- flag = !flag;
- res.add(resTemp);
- printS.clear();
- printS.addAll(temp);
- temp.clear();
- resTemp = null;
- }
- return res;
- }
- private ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
- }
来源: http://www.bubuko.com/infodetail-3355977.html