力扣0116——填充每一个节点的下一个右侧指针

填充每一个节点的下一个右侧指针

难度：中等

题目描述

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

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

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

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

示例1

输入： root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]

示例2

输入： root = []
输出：[]

题解

直接使用双层列表，在其中赋值即可

想法代码

public class Node
{public int val;public Node left;public Node right;public Node next;public Node() { }public Node(int _val){val = _val;}public Node(int val, Node left, Node right, Node next){this.left = left;this.right = right;this.next = next;this.val = val;}
}public class Solution
{public static void Main(string[] args){Node root = new Node{val = 1,left = new Node{val = 2,left = new Node(4),right = new Node(5)},right = new Node{val = 3,left = new Node(6),right = new Node(7)}};Solution solution = new Solution();Node ans = solution.Connect(root);Console.WriteLine(ans.val);}public Node Connect(Node root){List<List<Node>> list = new List<List<Node>>();Travel(root, list, 0);for (int i = 0; i < list.Count; i++){for (int j = 0; j < list[i].Count - 1; j++){list[i][j].next = list[i][j + 1];}list[i][list[i].Count - 1].next = null;}return root;}public void Travel(Node root, List<List<Node>> list, int h){if (root == null){return;}if (list.Count <= h){list.Add(new List<Node>());}list[h].Add(root);Travel(root.left, list, h + 1);Travel(root.right, list, h + 1);}
}