leetcode-114 二叉树展开为链表

  • English:

leetcode-114 二叉树展开为链表

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

 

例如,给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6

将其展开为:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

思路: 对子树进行递归展开,当左右子树都展开完了以后,将左子树接到右子树,再将原来的右子树接上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

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

if root is None:
return

# 左右子树展开
self.flatten(root.left)
self.flatten(root.right)


left = root.left
right = root.right

# 将左子树接到根右侧节点
root.right = left
root.left = None

# 将原来的右子树接到现在右子树的末尾
p = root
while p.right:
p = p.right
p.right = right
-------The end of this article  Thank you for your reading-------
  • 本文作者: Eree
  • 本文链接: https://ereebay.me/posts/44923/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!