第103题：二叉树的锯齿形层次遍历

一．问题描述

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：

给定二叉树 [3,9,20,null,null,15,7],

9 20

15 7

返回锯齿形层次遍历如下：

[

[3],

[20,9],

[15,7]

]

二．解题思路

本题思路：采用递归+广度优先遍历的方法进行求解

步骤一：构建遍历函数(全局变量list存储数据，局部变量data存储当前的节点数，标记量mark判断是从左往右开始遍历，还是从右往左开始遍历)

步骤二：在递归函数中进行层序遍历，当遇到奇数层时，对data数据从左往右遍历得到数据，存储在list中,并将其各个子树从左往右存储到新data中，将标记mark=-1；

步骤三：在递归函数中进行层序遍历，当遇到偶数层时，对data数据从右往左遍历得到数据,存储在list中,并将其各个子树从左往右存储到新data中，将标记mark=-1；

步骤四：当data不为空时返回步骤二，当为空时返回list列表。

三．执行结果

执行用时 :1 ms, 在所有 java 提交中击败了100.00%的用户

内存消耗 :36 MB, 在所有 java 提交中击败了40.11%的用户

四． Java代码

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        
        List<List<Integer>> list=new ArrayList<List<Integer>>();
        if(root==null) {
            return list;
        }
        List<TreeNode> data=new ArrayList<TreeNode>();
        data.add(root);
        treeNo(list,data,1);
        return list;
    }
    public void treeNo(List<List<Integer>> list,List<TreeNode> data,int mark) {
        if(data.size()==0) {
            return;
        }
        List<TreeNode> tempdata=new ArrayList<TreeNode>();
        List<Integer> temp=new ArrayList<Integer>();
        if(mark==1) {    
            for(int i=0;i<data.size();i++) {
                temp.add(data.get(i).val);
                if(data.get(i).left!=null) {
                    tempdata.add(data.get(i).left);
                }
                if(data.get(i).right!=null) {
                    tempdata.add(data.get(i).right);
                }
            }
            mark=-1;
        }else {
            for(int i=data.size()-1,j=0;i>=0||j<data.size();i--,j++) {
                temp.add(data.get(i).val);
                if(data.get(j).left!=null) {
                    tempdata.add(data.get(j).left);
                }
                if(data.get(j).right!=null) {
                    tempdata.add(data.get(j).right);
                }
            }    
            mark=1;
        }
        list.add(temp);
        treeNo(list,tempdata,mark);
    }
}

第103题：二叉树的锯齿形层次遍历

相关推荐