116.md

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

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

---

:pencil2:描述

给定一棵二叉树，它的所有叶子节点都在同一层，每一个父节点都有两个子节点，填充它的next节点，使其next节点指向下一个右侧节点,初始状态下所有的next节点都为null。

---

:pencil2:题目实例

​

:pencil2:题目分析

对于左子节点，只要把它的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;
    }

联系

​