Day 14

剑指offer 32-1.从上到下打印二叉树

题目描述

思路–广度优先搜索（BFS）

借辅助队列来实现广度优先搜索

解答

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
         //判空：根结点为空时，返回空数组
        if(root==null) return new int[0];
         //初始化结果列表和辅助队列
            ArrayList<Integer> array=new ArrayList<>();
            Queue<TreeNode> queue=new LinkedList<>();
            queue.add(root);
        //循环：直到辅助队列为空
            while(! queue.isEmpty()){
                //出队列 -- 对应结点的值添加到列表 -- 对应结点的子节点入队列
                TreeNode node=queue.poll();
                array.add(node.val);
                if(node.left !=null) queue.add(node.left);
                if(node.right !=null) queue.add(node.right);

            }
            int [] res=new int[array.size()];
         //遍历获取结果列表的元素并存入结果数组，然后返回结果数组
            for(int i=0;i<array.size();i++){
                res[i]=array.get(i);
            }
            return res;
    }
}

剑指offer 32-2.从上到下打印二叉树

题目描述

解答

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode>queue =new LinkedList<>();
        List<List<Integer>> list=new ArrayList<>();
        if(root==null) return list;
        queue.add(root);
        while(!queue.isEmpty()){
            // 定义一个List保存每一行的节点值
            List<Integer> currentList=new ArrayList<>();
            // 保存每行的节点个数
            int len=queue.size();
            for(int i=0;i<len;i++){
                TreeNode node=queue.poll();
                currentList.add(node.val);
                if(node.left!=null) queue.add(node.left);
                if(node.right !=null) queue.add(node.right);
            }
            list.add(currentList);
        }
        return list;
    }
}

剑指offer 32-3.从上到下打印二叉树

题目描述

解答

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode>queue =new LinkedList<>();
        List<List<Integer>> list=new ArrayList<>();
        if(root==null) return list;
        queue.add(root);
        while(!queue.isEmpty()){
            // 定义一个LinkedList 双向队列，保存每一行的节点值
            LinkedList<Integer> currentList=new LinkedList<>();
            // 保存每行的节点个数
            int len=queue.size();
            for(int i=0;i<len;i++){
                TreeNode node=queue.poll();
                //如果是双数行，逆向add
                if(list.size()%2==0){
                    currentList.addLast(node.val);
                }else{
                    currentList.addFirst(node.val);
                }
                if(node.left!=null) queue.add(node.left);
                if(node.right !=null) queue.add(node.right);
            }
            list.add(currentList);
        }
        return list;
    }
}