原题
给定一个二叉树
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/
相关推荐
-
leetcode12-整数转罗马数字
原题 罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如， 罗马数字 2...
-
leetcode24-两两交换链表中的节点
原题 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 示例: 给定 1->2->3->...
-
leetcode18-四数之和
原题 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 ta...
-
leetcode136-只出现一次的数字
原题 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗...
-
leetcode221-最大正方形
原题 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。 示例: 输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 ...
-
leetcode1162-地图分析
原题 你现在手里有一份大小为 N x N 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域...
-
leetcode409-最长回文串
原题 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。 在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。 注意:假设字符串的长...
-
leetcode328-奇偶链表
原题 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空...
-
leetcode121-买卖股票的最佳时机
原题 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。 注意你不能在...
-
leetcode1071-字符串的最大公因子
原题 对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。 返回最长字符串 X，要求满足 X 能除尽 ...