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

悠悠 2022-12-09 14:58 116阅读 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);
    
        }
    }