Leetcode基础刷题之PHP解析(116. Populating Next Right Pointers in Each )

上一题链接Leetcode基础刷题之PHP解析( 115. Distinct Subsequences)


613672242053b9d24351b8ddebe1e67c.png


题目描述

给定一棵二叉树,它的所有叶子节点都在同一层,每一个父节点都有两个子节点,填充它的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;
    }

上一篇: Leetcode PHP题解--D114 268. Missing Number

下一篇: Leetcode基础刷题之PHP解析(117. Populating Next Right Pointers in Each Node II)