剑指 Offer 32 - I. 从上到下打印二叉树-蒲公英云

剑指 Offer 32 - I. 从上到下打印二叉树

悠悠 2022-12-09 14:58 187阅读 0赞

题目：
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

例如:

给定二叉树: [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
返回：
[3,9,20,15,7]

提示：

节点总数 <= 1000

题解:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution { 
    //用来存在节点
    List<ArrayList<Integer>> list = new ArrayList();
    public int[] levelOrder(TreeNode root) { 
        List<Integer> tmp = new ArrayList();
       // int len = list.size();
        helper(root,0);
        //for(int i = 0; i< len;i++)这里的len固定了，不可以这么写
        for(int i = 0; i< list.size();i++){ 
            tmp.addAll(list.get(i));
        }
        //把list转换为数组
        int n = tmp.size();
        int[] res = new int[n];
        for(int i = 0; i< n; i++) { 
            res[i] = tmp.get(i);
        }
        return res;
    }
    public void helper(TreeNode node,int k){ 
        if(node == null) { 
            return;
        }
        //k表示层从0开始数的，如果k大于list的长度，表示k已经到了下一层，需要初始化下一层
        if(k >= list.size() ) { 
            list.add(new ArrayList());
        }
        //把node节点加入到第k层
        list.get(k).add(node.val);
        helper(node.left,k+1);
        helper(node.right,k+1);
    }
}