[leetcode]117. Populating Next Right Pointers in Each NodeII用next填充同层相邻节点
2024-08-31 01:29:23
Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:
- You may only use constant extra space.
- Recursive approach is fine, implicit stack space does not count as extra space for this problem.
Example:
Given the following binary tree,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
题意：
给定一个任意二叉树，其中每个节点都有next指针。
设法将next指针指向同一层右侧相邻节点。
思路：
递归，解法很巧妙。
以 1 为curr，用pre来连接curr.left：2 和 curr.right：3。因为此时根节点 1的next指向null, 退出for循环
1 ( curr )--->null
/ \
dummy(-1):pre--> 2---> 3
/ \ \
4 5 7 递归调用connect(dummy.next)，因为dummy.next指向2，此时 2 为curr。用pre来连接curr.left：4 和 curr.right：5。
1
/ \
2（curr）---> 3
/ \ \
dummy(-1):pre--> 4--->5 7
继续走for循环， curr = curr.next, 此时curr为3。 继续用pre连接 curr.left（3的左子树为Null） 和 curr.right：7。
1
/ \
2 ---> 3(curr)
/ \ \
dummy(-1):pre--> 4--->5 --->7
因为此时curr的next指向null, 退出for循环。
继续递归调用connect(dummy.next)... 直至 root == null， return
代码：
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null) return;
TreeLinkNode dummy = new TreeLinkNode(-1);
for (TreeLinkNode curr = root, prev = dummy;
curr != null; curr = curr.next) {
if (curr.left != null){
prev.next = curr.left;
prev = prev.next;
}
if (curr.right != null){
prev.next = curr.right;
prev = prev.next;
}
}
connect(dummy.next);
}
}
最新文章
- Mac OS 使用 Vagrant 管理虚拟机（VirtualBox）
- c#泛型的使用[转]
- jQuery源码分析系列(34) : Ajax - 预处理jsonp
- What does "size" in int(size) of MySQL mean?
- C# String 前面不足位数补零的方法
- 初遇 dotcloud
- linux 运维必备150个命令
- POJ 1961 Period( KMP )*
- css中文本框与按钮对不齐解决方案
- Apache+Tomcat +mod_proxy集群负载均衡及session
- [Angular 2] Using ng-for to repeat template elements
- sqlcipher for android
- js 停止事件冒泡 阻止浏览器的默认行为（阻止a标签跳转 ）
- spring-boot-devtools
- NO.7 项目需求分析
- CentOS7 安装Redis Cluster集群
- HDU2034
- 9、js扩展
- 14.2.4HTML5约束API验证
- shell中调用R语言并传入参数的两种步骤