关于java:算法入门之广度优先

树结构

为了更好的解说广度优先，先带大家看一下java实现树的树结构

//树结构public class TreeNode {    int val;    TreeNode left;    TreeNode right;    TreeNode() {    }    TreeNode(int val) {        this.val = val;    }    TreeNode(int val, TreeNode left, TreeNode right) {        this.val = val;        this.left = left;        this.right = right;    }}

思路

看到树这种构造，首先思考深度优先，其次能够思考用队列实现的广度优先。

队列版本的广度优先模板

    //广度优先万能模板    while (!queue.isEmpty()) {            TreeNode treeNode = queue.poll();            //以后节点解决逻辑            if (treeNode.left != null) {                queue.add(treeNode.left);            }            if (treeNode.right != null) {                queue.add(treeNode.right);            }        }

做题前先写下这个模板，而后依据题目往里面套,做适当变形即可。

实际

题目

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

先写模板

      while (!queue.isEmpty()) {            TreeNode treeNode = queue.poll();            //以后节点解决逻辑            if (treeNode.left != null) {                queue.add(treeNode.left);            }            if (treeNode.right != null) {                queue.add(treeNode.right);            }        }

模板变形

首先依据题意补充代码，套入下面的逻辑，造成办法

 public List<List<Integer>> levelOrder(TreeNode root) {        Queue<TreeNode> queue = new LinkedList<>();        if (root == null) {            return new LinkedList<>();        }        queue.add(root);        while (!queue.isEmpty()) {                TreeNode treeNode = queue.poll();                if (treeNode.left != null) {                    queue.add(treeNode.left);                }                if (treeNode.right != null) {                    queue.add(treeNode.right);                }            }        }        return null;    }

其次，思考到题目要求输入后果，那么就用list保留treeNode的值
最初，思考到层序遍历输入后果，while循环外面再嵌套一层逻辑

最终后果

public List<List<Integer>> levelOrder(TreeNode root) {        Queue<TreeNode> queue = new LinkedList<>();        if (root == null) {            return new LinkedList<>();        }        queue.add(root);        List<List<Integer>> lists = new LinkedList<>();        while (!queue.isEmpty()) {            List<Integer> list = new LinkedList<>();            int i = queue.size();            for (int i1 = 0; i1 < i; i1++) {                TreeNode treeNode = queue.poll();                list.add(treeNode.val);                if (treeNode.left != null) {                    queue.add(treeNode.left);                }                if (treeNode.right != null) {                    queue.add(treeNode.right);                }            }            lists.add(list);        }        return lists;    }