114. 二叉树展开为链表 [medium]

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

给定一个二叉树，原地将它展开为一个单链表。

例如，给定二叉树

将其展开为：

通过次数50,807 | 提交次数73,053

Second Try

2020-08-02

每日打卡题目，重做一遍。用递归方法，明显比First Try里面用栈模拟深度递归的写法慢多了，问题在于查找left分支的最后一个元素。

class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        
        def dfs(node):
            if not node:
                return 

            dfs(node.left)
            dfs(node.right)
            
            left = node.left 
            right = node.right
            node.left = None 
            if left:
                node.right = left 
                while node.right:
                    node = node.right 
            node.right = right 
        
        dfs(root)

执行用时：76 ms, 在所有 Python3 提交中击败了5.64%的用户
内存消耗：14.5 MB, 在所有 Python3 提交中击败了50.00%的用户

First Try

2020-07-17

一开始以为是转换为真的链表，写完测试才发现本质上还是一棵树，只是都放在右节点。

观察发现转化的顺序是按照前序深度优先的方式深入的，立马想到递归和迭代两种方式。

用递归方式，发现前后节点很难处理，写起来很别扭进行不下去。改成迭代模式后发现非常自然，尤其是添加了个prenode作为引导，前后关系就很容易了。

果然写起来别扭的方式，一般都是没有找到正确的方法。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        # 感觉就是深度递归的方式啊
        prenode = TreeNode(None)
        stack = [root]
        while len(stack):
            node = stack.pop()
            if not node:
                continue 
            left, right = node.left, node.right 
            prenode.right = node 
            prenode = node
            stack.append(node.right)
            stack.append(node.left)
            prenode.left = None 
            prenode.right = None 

执行用时：20 ms, 在所有 Python 提交中击败了96.31%的用户
内存消耗：13.5 MB, 在所有 Python 提交中击败了33.33%的用户

114. 二叉树展开为链表 [medium]​

Second Try​

First Try​

114. 二叉树展开为链表 [medium]

Second Try

First Try