美文网首页
114. Flatten Binary Tree to Link

114. Flatten Binary Tree to Link

作者: JERORO_ | 来源:发表于2018-06-20 14:01 被阅读0次

    问题描述

    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!

    相关文章

      网友评论

          本文标题:114. Flatten Binary Tree to Link

          本文链接:https://www.haomeiwen.com/subject/vkztyftx.html