package pp.arithmetic.leetcode;

import pp.arithmetic.Util;
import pp.arithmetic.model.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * Created by wangpeng on 2019-07-27.
 * 102. 二叉树的层次遍历
 * <p>
 * 给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
 * <p>
 * 例如:
 * 给定二叉树: [3,9,20,null,null,15,7],
 * <p>
 *  3
 * / \
 * 9  20
 *  /  \
 * 15   7
 * 返回其层次遍历结果：
 * <p>
 * [
 * [3],
 * [9,20],
 * [15,7]
 * ]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _102_levelOrder {

    public static void main(String[] args) {
        _102_levelOrder levelOrder = new _102_levelOrder();
        List<List<Integer>> lists = levelOrder.levelOrder(Util.generateTreeNode());
        for (int i = 0; i < lists.size(); i++) {
            Util.printList(lists.get(i));
        }
    }

    /**
     * 解题思路：
     * 按层次遍历，类似于BFS，用一个队列保存遍历结果
     * 1.将（根）节点存入队列
     * 2.将队列中数据取空
     * 3.将取出的treeNode的左右子树存入队列并将结果存入结果集
     * 4.重复1-3直到队列无数据
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new ArrayDeque<>();
        //1
        queue.add(root);
        //4
        while (!queue.isEmpty()) {
            List<TreeNode> list = new ArrayList<>();
            //2
            while (!queue.isEmpty()) {
                list.add(queue.poll());
            }
            //3
            if (list.size() > 0) {
                List<Integer> addList = new ArrayList<>();
                for (int i = 0; i < list.size(); i++) {
                    TreeNode treeNode = list.get(i);
                    addList.add(treeNode.val);
                    if (treeNode.left != null) queue.add(treeNode.left);
                    if (treeNode.right != null) queue.add(treeNode.right);
                }
                result.add(addList);
            }
        }
        return result;
    }
}

@@ -926,22 +926,211 @@
       %7D%0A
+        List%3CList%3CInteger%3E%3E lists2 = levelOrder.levelOrder2(Util.generateTreeNode());%0A        for (int i = 0; i %3C lists2.size(); i++) %7B%0A            Util.printList(lists2.get(i));%0A        %7D%0A
     %7D%0A
-
 %0A    /**
@@ -1282,16 +1282,108 @@
 %0A     *%0A
+     * %E4%BC%98%E5%8C%96%EF%BC%9A%E5%8F%AF%E4%BB%A5%E6%8A%8A2-3%E5%90%88%E5%B9%B6%E6%88%90%E4%B8%80%E6%AD%A5%EF%BC%8C%E4%BD%A0%E4%BC%9A%E5%92%8B%E5%BC%84%EF%BC%9F%0A     * %E4%BC%98%E5%8C%96%E6%96%B9%E6%A1%88%7B@link _102_levelOrder#levelOrder2(TreeNode)%7D%0A     *%0A
      * @
@@ -2335,24 +2335,24 @@
 d(addList);%0A
-
             
@@ -2391,11 +2391,879 @@
 t;%0A    %7D
+%0A%0A    /**%0A     * %E4%BC%98%E5%8C%96%EF%BC%9A%E5%B0%862-3%E5%90%88%E5%B9%B6%0A     *%0A     * @param root%0A     * @return%0A     */%0A    public List%3CList%3CInteger%3E%3E levelOrder2(TreeNode root) %7B%0A        List%3CList%3CInteger%3E%3E result = new ArrayList%3C%3E();%0A        if (root == null) return result;%0A        Queue%3CTreeNode%3E queue = new ArrayDeque%3C%3E();%0A        //1%0A        queue.add(root);%0A        //4%0A        while (!queue.isEmpty()) %7B%0A            List%3CInteger%3E addList = new ArrayList%3C%3E();%0A            //2-3%0A            int depth = queue.size();%0A            for (int i = 0; i %3C depth; i++) %7B%0A                TreeNode treeNode = queue.poll();%0A                addList.add(treeNode.val);%0A                if (treeNode.left != null) queue.add(treeNode.left);%0A                if (treeNode.right != null) queue.add(treeNode.right);%0A            %7D%0A            if (addList.size() %3E 0) result.add(addList);%0A        %7D%0A        return result;%0A    %7D
 %0A%7D%0A

优化_102_levelOrder