114. Flatten Binary Tree to Linked List

问题描述

Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:

Before.png

After.png

思路

1. 利用min heap的特点，右>左
   即right subtree的任意一个node，一定大于left subtree中的max_node
2. 从Before.png的1(即root)开始，将其left subtree在不违反min heap定义的前提下，移动到右边

具体操作

1. 用curNode记录当前正在操作的node
2. 走到curNode的left subtree的max_node, 并将curNode的整棵right_subtree，移到max_node的右边【Solution.png第一个】
3. 此时curNode没有right subtree，我们把它当前的整棵left subtree移动成它的right subtree【Solution.png第二个】
4. curNode = curNode.right，并循环这个流程直到没有curNode

Solution.png

    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        curNode = root
        while curNode:
            if curNode.left: 
                pre = curNode.left
                while pre.right:
                    pre = pre.right
                pre.right = curNode.right 
                curNode.right = curNode.left
                curNode.left = None
            curNode = curNode.right

参考连接

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/discuss/37010/Share-my-simple-NON-recursive-solution-O(1)-space-complexity!