【LeetCode面试经典150题】117. 填充每个节点的下一个右侧节点指针 II

一、题目

• 117. 填充每个节点的下一个右侧节点指针 II - 力扣（LeetCode）

• 给定一个二叉树：

struct Node {int val;Node *left;Node *right;Node *next;
}

• 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

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

二、思路

1. 由于涉及树的层级遍历，应该使用深度优先搜索，这样可以方便的操作同一层的数据；
2. 建立一个List用于存放树每层的当前操作节点，便于操作其next结点；
3. 先dfs左子树，并将搜索到的数据放入List中，此时List的大小即为树的深度，且其中的元素即为树的不同深度的最左端点；
4. dfs触底为null即返回，此时开始检索最底层的右子树，层层向上检索，每检索到一个结点，就将数组中存放的结点next值设置为当前结点，并更新数组当前深度的元素为当前结点，如此递归至右子树的最右一个null结点为止，next都被填充完成；

三、解法

解法一

class Solution {private final List<Node> NODE_LIST = new ArrayList<>();public Node connect(Node root) {dfs(root, 0);return root;}private void dfs(Node node, Integer depth) {if (node == null) {return;}if (depth == NODE_LIST.size()) {// 1. 现在的node是最深一层的最左边的结点NODE_LIST.add(node);} else {// 2. 现在的node是最左边结点的next结点NODE_LIST.get(depth).next = node;// 3. 更新当前node为node.nextNODE_LIST.set(depth, node);}dfs(node.left, depth + 1);dfs(node.right, depth + 1);}
}