数据结构 10. 二叉树
程序员文章站
2022-03-13 10:37:41
...
Leetcode部分二叉树相关练习
一、二叉树
1. 定义
二叉查找树（Binary Search Tree），又称为二叉搜索树、二叉排序树。其或者是一棵空树；或者是具有以下性质的二叉树：
- 若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值
- 若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值
- 左、右子树也分别为二叉排序树
类（TreeNode）：定义二叉搜索树各个节点
在该类中，分别存放节点本身的值，以及其左子节点，右子节点，根节点的值。
2. 实现一个二叉查找树，并且支持插入、删除、查找操作
2.1 查找和插入
当二叉查找树不为空时：
- 首先将给定值与根结点的关键字比较，若相等，则查找成功
- 若小于根结点的关键字值，递归查左子树
- 若大于根结点的关键字值，递归查右子树
- 若子树为空，查找不成功
二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径*问的最后一个结点的左孩子或右孩子结点。如下图所示：
2.2 删除
二叉查找树的删除操作分为三种情况：
- 如果待删除的节点是叶子节点，那么可以立即被删除，如下图所示：
2. 如果节点只有一个儿子，则将此节点parent的指针指向此节点的儿子，然后删除节点，如下图所示：
- 如果节点有两个儿子，则将其右子树的最小数据代替此节点的数据，并将其右子树的最小数据删除，如下图所示：
3. 实现二叉树前、中、后序以及按层遍历
3.1 先序遍历
访问顺序如下：
- 访问根节点
- 先序遍历左子树
- 先序遍历右子树
以图 1为例，访问顺序为：4，2，1，3，5，6
3.2 中序遍历
访问顺序如下：
- 中序遍历左子树
- 访问根节点
- 中序遍历右子树
以图 1为例，访问顺序为：1，2，3，4，5，6
3.3 后序遍历
访问顺序如下：
- 后序遍历左子树
- 后序遍历右子树
- 访问根节点
以图 1为例，访问顺序为：1，3，2，6，5，4
# encoding: utf-8
class Node:
def __init__(self, data):
self.data = data
self.lchild = None
self.rchild = None
class BST:
def __init__(self, node_list):
self.root = Node(node_list[0])
for data in node_list[1:]:
self.insert(data)
# 搜索
def search(self, node, parent, data):
if node is None:
return False, node, parent
if node.data == data:
return True, node, parent
if node.data > data:
return self.search(node.lchild, node, data)
else:
return self.search(node.rchild, node, data)
# 插入
def insert(self, data):
flag, n, p = self.search(self.root, self.root, data)
if not flag:
new_node = Node(data)
if data > p.data:
p.rchild = new_node
else:
p.lchild = new_node
# 删除
def delete(self, root, data):
flag, n, p = self.search(root, root, data)
if flag is False:
print "无该关键字，删除失败"
else:
if n.lchild is None:
if n == p.lchild:
p.lchild = n.rchild
else:
p.rchild = n.rchild
del p
elif n.rchild is None:
if n == p.lchild:
p.lchild = n.lchild
else:
p.rchild = n.lchild
del p
else: # 左右子树均不为空
pre = n.rchild
if pre.lchild is None:
n.data = pre.data
n.rchild = pre.rchild
del pre
else:
next = pre.lchild
while next.lchild is not None:
pre = next
next = next.lchild
n.data = next.data
pre.lchild = next.rchild
del p
# 先序遍历
def preOrderTraverse(self, node):
if node is not None:
print node.data,
self.preOrderTraverse(node.lchild)
self.preOrderTraverse(node.rchild)
# 中序遍历
def inOrderTraverse(self, node):
if node is not None:
self.inOrderTraverse(node.lchild)
print node.data,
self.inOrderTraverse(node.rchild)
# 后序遍历
def postOrderTraverse(self, node):
if node is not None:
self.postOrderTraverse(node.lchild)
self.postOrderTraverse(node.rchild)
print node.data,
a = [49, 38, 65, 97, 60, 76, 13, 27, 5, 1]
bst = BST(a) # 创建二叉查找树
bst.inOrderTraverse(bst.root) # 中序遍历
bst.delete(bst.root, 49)
print
bst.inOrderTraverse(bst.root)
4. 练习
98. 验证二查搜索树
[https://leetcode-cn.com/problems/validate-binary-search-tree/]
题目描述
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
代码实现
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isValidBST(self, root: TreeNode,min=None,max=None) -> bool:
if root==None:
return True
if min!=None and min>=root.val:
return False
if max!=None and max<=root.val:
return False
return self.isValidBST(root.left,min=min,max=root.val) and self.isValidBST(root.right,min=root.val,max=max)
102. 二叉树的层次遍历
[https://leetcode-cn.com/problems/binary-tree-level-order-traversal/submissions/]
题目描述
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
代码实现
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
res = []
if not root:
return res
temp = [root]
while temp:
cur = []
next_temp = []
for node in temp:
cur.append(node.val)
if node.left:
next_temp.append(node.left)
if node.right:
next_temp.append(node.right)
res.append(cur)
temp = next_temp
return res
107. 二叉树的层次遍历 II
[https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/]
题目描述
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
代码实现
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if root == None:
return []
stack = [root]
res = []
while len(stack) != 0:
tmp = []
res_each = []
for i in stack:
res_each.append(i.val)
if i.left != None:
tmp.append(i.left)
if i.right != None:
tmp.append(i.right)
stack = tmp
res.insert(0,res_each)
return res
226. Invert Binary Tree（翻转二叉树）
[https://leetcode-cn.com/problems/invert-binary-tree/]
题目描述
代码实现
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if root==None:
return None
root.left,root.right=root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
104. Maximum Depth of Binary Tree（二叉树的最大深度）
[https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/submissions/]
题目描述
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
代码实现
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxDepth(self, root: TreeNode) -> int:
# 当当前根为空时返回：空树
if root is None:
return 0
# 当还能继续往下钻
return max(self.maxDepth(root.left), self.maxDepth(root.right))+1