首页 > 代码库 > Populating Next Right Pointers in Each Node II Leetcode Python

Populating Next Right Pointers in Each Node II Leetcode Python

2024-11-17 04:33:02   202人阅读

Follow up for problem "Populating Next Right Pointers in Each Node".


What if the given tree could be any binary tree? Would your previous solution still work?


Note:


You may only use constant extra space.
For example,
Given the following binary tree,
         1
       /  \
      2    3
     / \    \
    4   5    7
After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \

    4-> 5 -> 7 -> NULL

这题和原来题目的区别在于这里的tree有肯能不是full tree.或者有残缺。 所以最好的方法是level order travesral然后把每层的node从左边指向右边。

这里用了个额外的存储。所以空间复杂度为O(N)

一共需要遍历两遍第一遍是存储，第二遍是指针。所以时间复杂度为O(N)

code is as follow

# 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 solve(self,solution,level,root):
        if len(solution)<level+1:
            solution.append([])
        solution[level].append(root)
        if root.left:
            self.solve(solution,level+1,root.left)
        if root.right:
            self.solve(solution,level+1,root.right)
    def connect(self, root):
        if root==None:
            return root
        solution=[]
        level=0
        self.solve(solution,level,root)
        for level in range(len(solution)):
            for count in range(1,len(solution[level])):
                solution[level][count-1].next=solution[level][count]
            solution[level][-1].next=None
        return root



Populating Next Right Pointers in Each Node II Leetcode Python


联系
我们