3 Flatten A Binary Tree to Double Linked List

binary tree to doubly linked list.

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

思路：这道题是数flatten成单项链表，面试题目相当于是加强版。就是preorder里面加点料。需要注意的地方是我们这个 self.pre = root这里很精妙，相当于在flatten右边树之前，把左树的最后一个节点给存起来了。

class Solution(object):
    pre = None
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void 
        """
        if root:
            self.pre = root
            self.flatten(root.left)

            tmp = root.right
            root.right = root.left
            root.left = None
            self.pre.next = root.right

            self.flatten(tmp)
# 我觉得上面这种解法太飞了。我来写一个不那么飞的
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void 
        """
        if root:
            self.flatten(root.left)
            # find root tail of flattened left sub tree
            # construct the link list.
            if root.left:
                tail = root.left
                while tail.right:
                    tail = tail.right
                right = root.right
                root.right = root.left
                root.left = None
                tail.right = right
            self.flatten(root.right)

a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
b.left, b.right = a, c
s = Solution()
s.flatten(b)
head = b
print head.val, head.right.val, head.right.right.val

加强版：因为我们需要双向链表。所以要记录这个node的parent.因为Input变成了2个，所以我们需要新写一个helper function呢。

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    pre = None
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void 
        """
        self.helper(root, None)


    def helper(self, root, p):

        if root:

            self.pre = root
            self.helper(root.left, root)

            tmp = root.right
            root.right = root.left
            root.left = p
            self.pre.next = root.right

            self.helper(tmp, self.pre)


a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)

a.left, a.right = b, c

so = Solution()
so.flatten(a)
print a.val, a.right.val, a.right.left.val

再follow up一下。我们Inorder flatten BST 成double linked List. 具体题目在这里: https://www.geeksforgeeks.org/in-place-convert-a-given-binary-tree-to-doubly-linked-list/ 下面这种写法不太好。不过大体思想还不错。第二种方法用inorder的更好

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def tree2DoubleLinkedList(self, root):
        head = TreeNode(-1)
        l1, r1 = self.flatten(root.left)
        print l1.val, r1.val
        l2, r2 = self.flatten(root.right)

        root.left = r1
        r1.right = root
        root.right = l2
        l2.left = root
        l1.left = r2
        r2.right = l1
        head.right = r1

        return head

    def flatten(self, root):
        if not root.left and not root.right:
            return root, root

        if root:
            l1, r1 = self.flatten(root.left)
            l2, r2 = self.flatten(root.right)
            root.left = r1
            r1.right = root
            root.right = l2
            l2.left = root
            l1.left = r2
            r2.right = l1

a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
b.left, b.right = a, c
s = Solution()
head = s.tree2DoubleLinkedList(b)
print head.right.val, head.right.right.val, head.right.right.right.val, head.right.right.right.right.val

第二种解法

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def tree2DoubleLinkedList(self, root):
        self.head = None
        self.pre = None
        self.inorder(root)
        return self.head


    def inorder(self, root):
        if root:
            self.inorder(root.left)

            # save first inorder node as head
            if not self.head:
                self.head = root

            # construct double linked list
            if self.pre:
                self.pre.right = root
                root.left = self.pre
            self.pre = root

            # small trick connect first node with last node.
            self.head.left = root
            right = root.right
            root.right = self.head
            self.inorder(right)


a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
b.left, b.right = a, c
s = Solution()
head = s.tree2DoubleLinkedList(b)
print head.val, head.right.val, head.right.right.val, head.right.right.right.val