一、題目

• 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);}
}