荐 八十一、Python | Leetcode 二叉树系列（下篇）
@Author：Runsen
@Date：2020/7/6
人生最重要的不是所站的位置，而是内心所朝的方向。只要我在每篇博文中写得自己体会，修炼身心；在每天的不断重复学习中，耐住寂寞，练就真功，不畏艰难，奋勇前行，不忘初心，砥砺前行，人生定会有所收获，不留遗憾 （作者：Runsen ）
作者介绍：Runsen目前大三下学期，专业化学工程与工艺，大学沉迷日语，Python， Java和一系列数据分析软件。导致翘课严重，专业排名中下。.在大学60%的时间，都在CSDN。决定今天比昨天要更加努力。
前面文章，点击下面链接
今日，我决定继续更新Python教程，今天就开始了八十一、Python | Leetcode 二叉树系列（下篇）。作为一名 Python 程序员，如果把基础的数据结构与算法都自己亲自实现一遍，那么你已经比 90% 的 Python 程序员更优秀了。
文章目录
LeetCode 第 94题：二叉树的中序遍历
#给定一个二叉树，返回它的中序 遍历。
# 示例:
# 输入: [1,null,2,3]
# 1
# \
# 2
# /
# 3
#输出: [1,3,2]
# 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
# Related Topics 栈 树 哈希表
递归：中序遍历的顺序是左根右。使用递归解题，条件是：当前节点为空则返回；递归条件是遍历其左右子节点。先访问左子节点，接着将当前节点的值添加到结果数组，然后访问右子节点。
栈的题解：首先访问左子树，将左子树存入栈中，每次将栈顶元素存入结果，如果右子树为空，取出栈顶元素，如果当前元素为栈顶元素右子树，一直弹出至当前元素不为栈顶元素右子树(此处说明访问右子树，根节点已经被访问过，弹出即可)。如果节点右子树不为空，访问右子树，继续循环遍历左子树，存入栈中。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def helper(root):
if not root:
return
helper(root.left)
res.append(root.val)
helper(root.right)
helper(root)
return res
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = [] #结果列表
stack = [] #辅助栈
cur = root #当前节点
while stack or cur:
while cur: #一直遍历到最后一层
res.append(cur.val)
stack.append(cur)
cur = cur.left
top = stack.pop() #此时该节点的左子树已经全部遍历完
cur = top.right #对右子树遍历
return res
LeetCode 第 98题：验证二叉搜索树
#给定一个二叉树，判断其是否是一个有效的二叉搜索树。
# 假设一个二叉搜索树具有如下特征：
# 节点的左子树只包含小于当前节点的数。
# 节点的右子树只包含大于当前节点的数。
# 所有左子树和右子树自身必须也是二叉搜索树。
# 示例 1:
# 输入:
# 2
# / \
# 1 3
#输出: true
# 示例 2:
# 输入:
# 5
# / \
# 1 4
# / \
# 3 6
#输出: false
#解释: 输入为: [5,1,4,null,null,3,6]。
# 根节点的值为 5 ，但是其右子节点值为 4 。
# Related Topics 树 深度优先搜索
做这题，需要了解二叉搜索树的特点：
- 当前节点的左子树的所有节点的值都应该小于当前节点的值；
- 当前节点的右子树的所有节点的值都应该大于当前节点的值
为了简便，我们可以这么做：
在之前中介绍过二叉搜索树一个很重要的定义就是，对一棵二叉搜索树进行中序遍历(左->根->右)，遍历所得的节点序列是一个升序排列的序列。所以我们可以利用二叉搜索树的这个性质，来判断一个二叉搜索树是否合法，就是上面那题的变形。
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
#中序遍历，观察到中序遍历的顺序是左->中->右,也就是按照从小到大的顺序，因此这样思考题目就很好解了,按照中序遍历，将值依次存入列表中。最后判断
if not root:
return True
result = []
def middle_traversal(root):
if root.left:
middle_traversal(root.left)
result.append(root.val)
if root.right:
middle_traversal(root.right)
middle_traversal(root)
return result == sorted(result) and len(set(result)) == len(result)
# 下面是栈的题解
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
stack, preNum = [], float("-inf")
while len(stack) > 0 or root:
if root:
stack.append(root)
root = root.left
else:
root = stack.pop()
if root.val <= preNum:
return False
preNum = root.val
root = root.right
return True
LeetCode 第 105题：从前序与中序遍历序列构造二叉树
#根据一棵树的前序遍历与中序遍历构造二叉树。
# 注意:
#你可以假设树中没有重复的元素。
# 例如，给出
# 前序遍历 preorder = [3,9,20,15,7]
#中序遍历 inorder = [9,3,15,20,7]
# 返回如下的二叉树：
#
# 3
# / \
# 9 20
# / \
# 15 7
# Related Topics 树 深度优先搜索 数组
二叉树前序遍历：
- 先遍历根节点
- 再递归遍历左子树
- 最后递归遍历右子树
二叉树中序遍历：
- 先递归遍历左子树
- 再遍历根节点
- 最后递归遍历右子树
二叉树后序遍历：
- 先递归遍历左子树
- 再递归遍历右子树
- 最后遍历根节点
前序遍历和中序遍历二者之间的联系，二者相同的纽带为根节点，因此我们可以通过在前序遍历中定位到根节点，然后从中序遍历中根节点找到对应的index，从而可以知道左右子树分别的节点数目
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
index = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1:index+1], inorder[:index])
root.right = self.buildTree(preorder[index+1:], inorder[index+1:])
return root
LeetCode 第 106题：从中序与后序遍历序列构造二叉树
#根据一棵树的中序遍历与后序遍历构造二叉树。
# 注意:
#你可以假设树中没有重复的元素。
# 例如，给出
# 中序遍历 inorder = [9,3,15,20,7]
#后序遍历 postorder = [9,15,7,20,3]
# 返回如下的二叉树：
# 3
# / \
# 9 20
# / \
# 15 7
# Related Topics 树 深度优先搜索 数组
道理和上面的一样，从后序遍历中定位到根节点，然后从中序遍历中根节点找到对应的index，从而可以知道左右子树分别的节点数目。
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
# 实际上inorder 和 postorder一定是同时为空的，因此你无论判断哪个都行
if not inorder:
return None
root = TreeNode(postorder[-1])
i = inorder.index(root.val)
root.left = self.buildTree(inorder[:i], postorder[:i])
root.right = self.buildTree(inorder[i+1:], postorder[i:-1])
return root
本文地址：https://blog.csdn.net/weixin_44510615/article/details/107154809