关于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;
    }