117.md

:pencil2:Leetcode基础刷题之(117. Populating Next Right Pointers in Each Node II)

2019-08-13 吴亲库里 库里的深夜食堂

---

:pencil2:描述

这里是上一题的第二版，这道题让我们把二叉树每一个结点的下一个指针指向他的右侧结点，如果没有那么就是null

---

:pencil2:题目实例

​

:pencil2:题目分析

实现方法还是递归，确认层级的next指针，然后把右节点的next指针指向它，在把左节点的指针指向右节点，如果没有右节点，直接指向null。

    /**
     * @param Node $root
     * @return Node
     */
    function connect($root) {
        if(!$root) return null;
        $p=$root->next;
        while($p){
            if($p->left){
                $p=$p->left;
                break;
            }
            if($p->right){
                $p=$p->right;
                break;
            }
            $p=$p->next;
        }
       if($root->right) $root->right->next=$p;
       if($root->left) $root->left->next=$root->right??$p;
       $this->connect($root->right);
       $this->connect($root->left);
       return $root;
    }

---

联系

​