1、leetcode:114. 二叉树展开为链表
给定一个二叉树，原地将它展开为一个单链表。
例如，给定二叉树
1
/ \
2 5
/ \ \
3 4 6
将其展开为：
1
\
2
\
3
\
4
\
5
\
6
第一种思路：由于将节点展开之后会破坏二叉树的结构而丢失子节点的信息，因此前序遍历和展开为单链表分成了两步。
解题思路的关键点：
1）前序遍历产生的结果时，增加的是节点，不是节点的值
2）遍历完后对原数组直接进行遍历修改，注意左节点都是为空
代码如下：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
if not root:
return
#前序遍历结果
def pre(root:TreeNode):
if not root:
return
res.append(root)
pre(root.left)
pre(root.right)
return res
res=[]
res=pre(root)
k=len(res)
#原地展开
for i in range(1,k):
pre,cur=res[i-1],res[i]
pre.left=None
pre.right=cur
第二种思路：
之所以会在破坏二叉树的结构之后丢失子节点的信息，是因为在对左子树进行遍历时，没有存储右子节点的信息，在遍历完左子树之后才获得右子节点的信息。只要对前序遍历进行修改，在遍历左子树之前就获得左右子节点的信息，并存入栈内，子节点的信息就不会丢失，就可以将前序遍历和展开为单链表同时进行。
该做法不适用于递归实现的前序遍历，只适用于迭代实现的前序遍历。修改后的前序遍历的具体做法是，每次从栈内弹出一个节点作为当前访问的节点，获得该节点的子节点，如果子节点不为空，则依次将右子节点和左子节点压入栈内（注意入栈顺序）。
classSolution: defflatten(self, root: TreeNode)->None: """
Do not return anything, modify root in-place instead.
""" if not root:
return
stack = [root]
prev = None
while stack:
curr = stack.pop()
if prev:
prev.left = None
prev.right = curr
left, right = curr.left, curr.right
if right:
stack.append(right)
if left:
stack.append(left)
prev = curr
2、leetcode面试题 17.12. BiNode
二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。
返回转换后的单向链表的头节点。
注意：本题相对原题稍作改动
解题思路：
1）中序遍历产生有序数组
2）在递归的过程中，不断修改节点
修改当前节点
前一个节点指向当前节点
把当前节点赋给前一个节点
代码如下：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def convertBiNode(self, root: TreeNode) -> TreeNode:
self.pre=self.ans=TreeNode(-1)
def inorder(root: TreeNode):
if not root:
return
inorder(root.left)
root.left=None
self.pre.right=root
self.pre=root
inorder(root.right)
inorder(root)
return self.ans.right
网友评论