原题
给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
进阶：
+ 你只能使用常量级额外空间。
+ 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
示例：
输入： root = [1,2,3,4,5,null,7] 输出：[1,#,2,3,#,4,5,7,#] 解释： 给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
提示：
- 树中的节点数小于
6000 -100 <= node.val <= 100
解法
思想
我在leetcode116-填充每个节点的下一个右侧节点指针用的方法仍适用于该题
代码
class Solution {
List<Node> list;
public Node connect(Node root) {
list = new ArrayList<Node>();
dfs(root,0);
return root;
}
public void dfs(Node root,int depth){
if(root == null) return;
if(list.size()>depth){
Node node = list.get(depth);
node.next = root;
list.set(depth,root);
}
else list.add(root);
dfs(root.left,depth+1);
dfs(root.right,depth+1);
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode117-%e5%a1%ab%e5%85%85%e6%af%8f%e4%b8%aa%e8%8a%82%e7%82%b9%e7%9a%84%e4%b8%8b%e4%b8%80%e4%b8%aa%e5%8f%b3%e4%be%a7%e8%8a%82%e7%82%b9%e6%8c%87%e9%92%88ii/
相关推荐
-
leetcode622-设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是...
-
leetcode202-快乐数
原题 编写一个算法来判断一个数是不是“快乐数”。 一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无...
-
leetcode347-前K个高频元素
原题 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。 示例1： 输入： nums = [1,1,1,2,2,3], k = 2 输出： [1,2] 示例2： 输入： n...
-
leetcode118-杨辉三角
原题 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。在杨辉三角中，每个数是它左上方和右上方的数的和。 示例: 输入: 5 输出: [ [1], [1,1]...
-
leetcode21-合并两个有序链表
原题 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例： 输入： 1->2->4, 1->3->4 输出： 1->1->2->3-...
-
leetcode84-柱状图中最大的矩形
原题 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。 以上是柱状图的示例，其中每个柱子的宽...
-
leetcode300-最长上升子序列
原题 给定一个无序的整数数组，找到其中最长上升子序列的长度。 示例： 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,10...
-
leetcode387-字符串中的第一个唯一字符
原题 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。 案例: s = "leetcode" 返回 0. s = "loveleetcode"...
-
剑指offer04-二维数组中的查找
原题（来源Leetcode） 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个...
-
leetcode135-分发糖果
原题 老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。 你需要按照以下要求，帮助老师给这些孩子分发糖果： 每个孩子至少分配到 1 个...