#yyds干货盘点# LeetCode程序员面试金典：填充每个节点的下一个右侧节点指针 II

题目：

给定一棵二叉树：

struct Node {

int val;

Node *left;

Node *right;

Node *next;

}

填满它的每一个 next 指针，让指针指向下一个右节点。如果找不到下一个右节点，它将被发现 next 指针设置为 NULL 。

在初始状态下，所有next 所有的指针都设置为 NULL 。

示例 1：

输入：root = [1，2，3，4，5null,7]

输出:[1，#，2，3，#，4，5，7]

说明:给定二叉树如图: A 所示，你的函数应该填充它的每个函数 next 指针指向下一个右节点，如图所示 B 所示。序列化输出按层次遍历顺序(由 next "#"指针连接) 表示每层的末尾。

示例 2：

输入：root = []

输出：[]

代码实现：

// 102.二叉树的层序遍历class Solution {    public List<List<Integer>> resList = new ArrayList<List<Integer>>();    public List<List<Integer>> levelOrder(TreeNode root) {        ///checkFun01(root,0);        checkFun02(root);        return resList;    }    //DFS--递归方式    public void checkFun01(TreeNode node, Integer deep) {        if (node == null) return;        deep++;        if (resList.size() < deep) {            当层次增加时，list的Item也会增加，利用list的索引值进行层次定义            List<Integer> item = new ArrayList<Integer>();            resList.add(item);        }        resList.get(deep - 1).add(node.val);        checkFun01(node.left, deep);        checkFun01(node.right, deep);    }    //BFS--迭代-使用队列列列-使用队列列列-    public void checkFun02(TreeNode node) {        if (node == null) return;        Queue<TreeNode> que = new LinkedList<TreeNode>();        que.offer(node);        while (!que.isEmpty()) {            List<Integer> itemList = new ArrayList<Integer>();            int len = que.size();            while (len > 0) {                TreeNode tmpNode = que.poll();                itemList.add(tmpNode.val);                if (tmpNode.left != null) que.offer(tmpNode.left);                if (tmpNode.right != null) que.offer(tmpNode.right);                len--;            }            resList.add(itemList);        }    }}