首页 > 代码库 > [leetcode]Populating Next Right Pointers in Each Node @ Python [逻辑动力学]

[leetcode]Populating Next Right Pointers in Each Node @ Python [逻辑动力学]

(坦率的说,这道题目感动了我, 让我这个编程新手体验到了逻辑的美)

原题地址:https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node/

题意:

         1       /        2    3     / \  /     4  5  6  7
变为:
         1 -> NULL       /        2 -> 3 -> NULL     / \  /     4->5->6->7 -> NULL

解题思路:这道题目充分展现了宏观和微观完美的在细节出水乳交融的具体过程.

1) 看到二叉树我们就想到需要使用递归的思路了。

2) 注意递归之外的细节:正式这些细节完成了实际的逻辑求解

我们以2号结点为例:为了繁衍next结点,仅需要处理两种微观情况:

case 1:  2 -> 3 :  

Solution:       root.left.next  = root.right

 

case 2:  2 -> 5 -> 6:  

Solution:       root.right.next = root.next.left if root.next else None   

      2 -> 3     / \  /     4->5->6
# Definition for a  binary tree node# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = None#         self.next = Noneclass Solution:    # @param root, a tree node    # @return nothing    def connect(self, root):        if root and root.left:            root.left.next  = root.right            root.right.next = root.next.left if root.next else None            self.connect(root.left)            self.connect(root.right)

 

参考致谢: 在[1]的基础上,更突出了细节的对偶处理

[1] http://www.cnblogs.com/zuoyuan/p/3745170.html           

 

[leetcode]Populating Next Right Pointers in Each Node @ Python [逻辑动力学]