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

114. Flatten Binary Tree to Link

作者: 云外雁行斜丶 | 来源:发表于2019-05-30 16:56 被阅读0次

    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:

        1
       / \
      2   5
     / \   \
    3   4   6
    

    The flattened tree should look like:

    1
     \
      2
       \
        3
         \
          4
           \
            5
             \
              6
    

    First

    根据栈的思想,通过深度优先遍历将所有的节点退出栈中,再由栈弹出每个节点进行拼接

    from quixote.structs.tree import TreeNode
    
    class Solution(object):
        def flatten(self, root):
            """
            :type root: TreeNode
            :rtype: None Do not return anything, modify root in-place instead.
            """
            self.stack = []
            self.dfs(root)
            print(self.stack)
            tmp = None
            while self.stack:
                node = self.stack.pop()
                node.right = tmp
                tmp = node
            return tmp
    
        def dfs(self, root):
            self.stack.append(root)
            if root.left:
                self.dfs(root.left)
            if root.right:
                self.dfs(root.right)
    

    相关文章

      网友评论

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

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