Leetcode部分二叉树相关练习

一、二叉树1. 定义2. 实现一个二叉查找树，并且支持插入、删除、查找操作2.1 查找和插入2.2 删除 3. 实现二叉树前、中、后序以及按层遍历3.1 先序遍历3.2 中序遍历3.3 后序遍历 4. 练习98. 验证二查搜索树102. 二叉树的层次遍历107. 二叉树的层次遍历 II226. Invert Binary Tree（翻转二叉树）104. Maximum Depth of Binary Tree（二叉树的最大深度）

一、二叉树

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