題目

114. 二叉樹展開為鏈表

題解

1. 遞歸

1. 先序遍歷
2. 然后將數組操作

for i in range(1, len(res)):prev, curr = res[i - 1], res[i]prev.left = Noneprev.right = curr

# 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: Optional[TreeNode]:rtype: None Do not return anything, modify root in-place instead."""res = []def dfs(node):if node is None:returnres.append(node)dfs(node.left)dfs(node.right)dfs(root)for i in range(1, len(res)):prev, curr = res[i - 1], res[i]prev.left = Noneprev.right = curr

2. 迭代

1. 先序遍歷
2. 與1方法一樣

# 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: Optional[TreeNode]:rtype: None Do not return anything, modify root in-place instead."""if not root:return rootres = []stack = []stack.append(root)while stack:node = stack.pop()res.append(node)if node.right:stack.append(node.right)if node.left:stack.append(node.left)for i in range(1, len(res)):prev, curr = res[i - 1], res[i]prev.left = Noneprev.right = curr

3. 右指針重排，始終將右子樹添加到左子樹的最右

# 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: Optional[TreeNode]:rtype: None Do not return anything, modify root in-place instead."""cur = rootwhile cur:if cur.left:pre = cur.leftwhile pre.right:pre = pre.rightpre.right = cur.rightcur.right =cur.leftcur.left = Nonecur = cur.right