首页 > 代码库 > 之字形打印二叉树

之字形打印二叉树

2024-09-14 00:44:47   230人阅读

题目：请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类

思路：leetcode上的最优解，思路就是dfs，而不是一层一层遍历，层数是偶数（0,2,4。。。）时，顺序添加相应的节点的数字，而奇数层时（1,3,5。。），每次插到arraylist最开头，也就是index为0的位置，ArrayList会扩充最前面的长度，就实现了转置

public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        travel(pRoot,res,0);
        return res;
    }
    private void travel(TreeNode curr,ArrayList<ArrayList<Integer>> res,int level){
        if(curr==null)return;
        if(res.size()<=level){
            ArrayList<Integer> newLevel=new ArrayList<>();
            res.add(newLevel);
        }
        ArrayList<Integer> collection=res.get(level);
       if(level%2==0) collection.add(curr.val);
        else collection.add(0,curr.val);
        
        travel(curr.left,res,level+1);
        travel(curr.right,res,level+1);
    }

 

之字形打印二叉树


联系
我们