初学python的我开始Leetcode题8-4
提示：100道LeetCode热题-8-4主要是二叉树相关，包括三题：二叉树的右视图、二叉树展开为链表、从前序与中序遍历序列构造二叉树。由于初学，所以我的代码部分仅供参考。
前言
继续二叉树~
上海雨好大/(ㄒoㄒ)/~~打油一首：方从雨中行，落花湿沾衣。裤重步难移，鞋履尽尘泥。
提示：以下是本篇文章正文内容，下面结果代码仅供参考
题目1：二叉树的右视图
1.题目要求：
题目如下：
给定一个二叉树的 根节点
root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。示例 1：
输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]
解释：
示例 2：
输入：root = [1,2,3,4,null,null,null,5]
输出：[1,3,4,5]
解释：
示例 3：
输入：root = [1,null,3]
输出：[1,3]
示例 4：
输入：root = []
输出：[]
提示:
- 二叉树的节点个数的范围是
[0,100]-100 <= Node.val <= 100
代码框架已经提供如下：
# 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 rightSideView(self, root):
"""
:type root: Optional[TreeNode]
:rtype: List[int]
"""
2.结果代码：
from collections import dequeclass Solution(object):def rightSideView(self, root):""":type root: TreeNode:rtype: List[int]"""if not root:return []result = []queue = deque([root])while queue:level_length = len(queue)for i in range(level_length):node = queue.popleft()# 如果是当前层的最后一个节点，记录其值if i == level_length - 1:result.append(node.val)# 将左子节点和右子节点依次加入队列if node.left:queue.append(node.left)if node.right:queue.append(node.right)return result说明：
这题最大的提升点是直接记录每层的最后一个节点：
-
在每一层的遍历中，直接检查当前节点是否是该层的最后一个节点。如果是，则将其值加入结果列表。
-
这样可以避免额外的
level列表，直接在遍历时处理。
题目2：二叉树展开为链表
1.题目要求：
题目如下：
给你二叉树的根结点
root，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用
TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。- 展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例 1：
输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6]示例 2：
输入：root = [] 输出：[]示例 3：
输入：root = [0] 输出：[0]提示：
- 树中结点数在范围
[0, 2000]内-100 <= Node.val <= 100进阶：你可以使用原地算法（
O(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.
"""
2.结果代码：
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:# 找到左子树的最右节点runner = cur.leftwhile runner.right:runner = runner.right# 将右子树接到左子树的最右节点上runner.right = cur.right# 将左子树移到右子树的位置，并将左子树置为空cur.right = cur.leftcur.left = None# 移动到下一个节点cur = cur.right说明：
利用了 Morris 遍历的思想，通过调整指针来实现原地展开二叉树为单链表，时间复杂度为 O(n)，空间复杂度为 O(1)。
代码解释：
-
初始化：
-
从根节点
root开始，使用cur指针遍历二叉树。
-
-
处理左子树：
-
如果当前节点
cur有左子树：-
使用
runner指针找到左子树的最右节点。 -
将当前节点的右子树接到左子树的最右节点的右子树上。
-
将当前节点的左子树移到右子树的位置，并将左子树置为空。
-
-
-
移动到下一个节点：
-
将
cur指针移动到下一个节点（即当前节点的右子树）。
-
题目3：从前序与中序遍历序列构造二叉树
1.题目要求：
题目如下：
给定两个整数数组
preorder和inorder，其中preorder是二叉树的先序遍历，inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]示例 2:
输入: preorder = [-1], inorder = [-1] 输出: [-1]提示:
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder和inorder均 无重复 元素inorder均出现在preorderpreorder保证 为二叉树的前序遍历序列inorder保证 为二叉树的中序遍历序列
代码框架已经提供如下：
# 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 buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: Optional[TreeNode]
"""
2.结果代码：
class Solution(object):def buildTree(self, preorder, inorder):""":type preorder: List[int]:type inorder: List[int]:rtype: Optional[TreeNode]"""inorder_index = {val: i for i, val in enumerate(inorder)}def build(pre_start, pre_end, in_start, in_end):if pre_start > pre_end:return Noneroot_val = preorder[pre_start]root = TreeNode(root_val)root_index = inorder_index[root_val]left_tree_size = root_index - in_startroot.left = build(pre_start + 1, pre_start + left_tree_size, in_start, root_index - 1)root.right = build(pre_start + left_tree_size + 1, pre_end, root_index + 1, in_end)return rootreturn build(0, len(preorder) - 1, 0, len(inorder) - 1)使用哈希表存储中序遍历的索引，时间复杂度是 O(n)，空间复杂度是 O(n)。
总结
针对二叉树的三种题型进行了学习，了解了部分有关二叉树与python的相关知识，大家加油！