leetCode ✏Leetcode基础刷题之(116. Populating Next Right Pointers in Each)
✏描述
给定一棵二叉树，它的所有叶子节点都在同一层，每一个父节点都有两个子节点，填充它的next节点，使其next节点指向下一个右侧节点,初始状态下所有的next节点都为null。
✏题目实例
✏题目分析
对于左子节点，只要把它的next指针指向他的兄弟节点，对于右子节点，需要去判断父节点的next指针是否为空，如果不为空，那么$root->right->next=$root->next->left,这样公式就出来了。
/**
* @param Node $root
* @return Node
*/
function connect($root) {
if(!$root) return null;
if($root->left) $root->left->next=$root->right;
if($root->right) $root->right->next=$root->next?$root->next->left:null;
$this->connect($root->left);
$this->connect($root->right);
return $root;
}
看到一个思路是用两个指针，一个指针标记每一层起始的节点，另一个指针用来遍历
/**
* @param Node $root
* @return Node
*/
function connect($root) {
if(!$root) return null;
$start=$root;
$cur=null;
while($start->left){
$cur=$start;
while($cur){
$cur->left->next=$cur->right;
if($cur->next) $cur->right->next=$cur->next->left;
$cur=$cur->next;
}
$start=$start->left;
}
return $root;
}
转载链接：https://leetcode.cn/
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)