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

Created 5 years ago by 吴亲库里, Updated 5 years ago Revision #1 2409 views 1 likes 0 collects

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

题目描述

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

Github整理地址:https://github.com/wuqinqiang/leetcode-php