树——populating-next-right-pointers-in-each-node(填充每个节点的next指针)
2024-09-05 20:35:54
问题:
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 toNULL.
Initially, all next pointers are set toNULL.
Note:
- You may only use constant extra space.
- You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
1
/ \
2 3
/ \ / \
4 5 6 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ / \
4->5->6->7 -> NULL
思路:
首先判断根节点是否为null,如果是,return;如果不是,继续。
设置节点node,用来指向每层的第一个节点;设置节点next,用来指向该层的每个节点。
当node的左孩子存在时,使用next来遍历该层的其它节点:
(1)让node左孩子的next指向node右孩子;
(2)若next.next不为null,让node右孩子的next指向next.next的左孩子。
代码:
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public void connect(TreeLinkNode root) {
if(root==null)
return;
root.next = null;
TreeLinkNode node = root, next = node;
while(node.left!=null){
next = node;
while(next!=null){
next.left.next = next.right;
if(next.next!=null)
next.right.next = next.next.left;
next = next.next;
}
node = node.left;
}
}
}
最新文章
- Linux-read命令
- poj3608Bridge Across Islands(凸包间最小距离)
- nyoj------79拦截导弹
- Solaris引导和关闭
- Proxifier设置代理
- Android getTopActivity的方法
- C/C++ 中 const 修饰符用法总结
- Spark算子--SortByKey
- 《SQL Server性能调优实战》知识点汇总
- 步步为营-87-imageAreaSelect插件使用(图片剪切)
- python之成员(面向对象)
- 解决*.props打开失败问题
- iOS8不能通过itms-services协议下载安装app
- TortoiseGit学习系列之TortoiseGit基本操作将提交到本地的项目推送到在线仓库(图文详解)
- 通用 CSS 笔记、建议与指导
- C# 读Autofac源码笔记(1)
- Jmeter运营活动并发测试—巧用集合点
- 在richtextbox中获取最真实的字符串像素大小
- os模块与 sys模块
- adb devices 找不到设备怎么办 --- 2