【LeetCode with Python】 116. Populating Next Right Pointers in Each Node

题目

原题页面:https://leetcode.com/problems/populating-next-right-pointers-in-each-node/
本文地址:http://leetcode.xnerv.wang/populating-next-right-pointers-in-each-node/
题目类型:Tree, Depth-first SearchTwo Pointers
难度评价:Medium
类似题目:(H) Populating Next Right Pointers in Each II Node, (M) Binary Tree Right Side View

Given a binary tree

struct TreeLinkNode {
TreeLinkNode left;
TreeLinkNode
right;
TreeLinkNode next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

*Note:


  • You may only use constant extra space.
  • You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

    For example,
    Given the following perfect binary tree,

           1<br/>
         /  \<br/>
        2    3<br/>
       / \  / \<br/>
      4  5  6  7<br/>
    

    After calling your function, the tree should look like:


           1 -> NULL<br/>
         /  \<br/>
        2 -> 3 -> NULL<br/>
       / \  / \<br/>
      4->5->6->7 -> NULL<br/>
    

分析

类似于层次遍历的方法,参考Binary Tree Level Order Traversal这道题的代码,其实就是在其基础上加上了对一层结点的next指针的处理逻辑。
此外,这道题的衍生版本Populating Next Right Pointers in Each Node II与本题的区别是,本题是完全二叉树,而Populating Next Right Pointers in Each Node II却可能是任意结构的二叉树。但本题的代码对于这两道题都可以通过。
(但是本题代码可能不符合题意要求,题目要求消耗常量空间)


代码

# Definition for a  binary tree node
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.next = None

class Solution:
    # @param root, a tree node
    # @return nothing
    def connect(self, root):
        if None == root:
            return [ ]
        reflist1 = [root]
        while True:
            reflist2 = [ ]
            for i in range(0, len(reflist1)):
                cur = reflist1[i]
                if None != cur.left:
                    reflist2.append(cur.left)
                if None != cur.right:
                    reflist2.append(cur.right)
            if 0 == len(reflist2):
                break
            len_l = len(reflist2)
            for i in range(0, len_l - 1):
                reflist2[i].next = reflist2[i + 1]
            reflist2[len_l - 1].next = None
            reflist1 = reflist2

results matching ""

    No results matching ""