''' 题目 给一个排序数组（从小到大），将其转换为一棵高度最小的排序二叉树。 注意事项 There may exist multiple valid solutions, return any of them. 样例 给出数组 [1,2,3,4,5,6,7], 返回 4 / \ 2 6 / \ / \ 1 3 5 7 [4,2,6,1,3,5,7] 思路 二叉排序树：若它的左子树上的所有节点的值均小于它的根节点的值；若它的右子树上的所有节点的值均大于于它的根节点值 思路：对已排序的数组得到中间值，然后分左右树，然后对左右树也是一样，找到中间值，分左右树。 注意的是每次得到的中间值都需要建立树，然后对其设置左右树 '''
"""
Definition of TreeNode:
"""
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
from queue import Queue
class Solution:
"""
@param: A: an integer array
@return: A tree node
"""
def sortedArrayToBST(self, A):
# write your code here
if A is None :return None
result = self.binCut(A,0,len(A)-1)
# print(result)
return result
def binCut(self,A,x,y):
if A is None:return None
root = None
if x < y:
# print('x=',x)
# print('y=',y)
mid = (x+y)//2
# print('mid=', mid)
root = TreeNode(A[mid])
root.left = self.binCut(A,x,mid-1)
root.right = self.binCut(A,mid+1,y)
if x == y:
root = TreeNode(A[x])
return root
############对二叉树进行搜索##############
class BinaryTree(object):
def __init__(self, root=None):
self.root = root
##############广度搜索#################
def breathSearth(self):
if self.root == None:
return None
retList = []
queue = Queue()
queue.put(self.root)
while queue.empty() is not True:
node = queue.get()
retList.append(node.val)
if node.left != None:
queue.put(node.left)
if node.right != None:
queue.put(node.right)
return retList
###############深度遍历##################
def DFS(self,root): # 递归实现深度优先遍历
if root == None:
return
# print(self.root.val)
self.DFS(root.left)
self.DFS(root.right)
# print(root.val,end=' ') #1 3 2 5 7 6 4 后序遍历
def DFS_STACK(self): # 基于栈数据结构实现的深度遍历
if self.root == None:
return
stack = []
new_stack=[]
stack.append(self.root)
while stack:
now_node = stack.pop()
new_stack.append(now_node.val) #[4, 2, 1, 3, 6, 5, 7] 前序遍历
# print(now_node.val)
if now_node.right != None:
stack.append(now_node.right)
if now_node.left != None:
stack.append(now_node.left)
return new_stack
'''
二叉树的深度优先遍历：
先序遍历：根->对左子树先序遍历->对右子树先序遍历
先访问根节点，再对左子树进行先序遍历（递归），最后对右子树进行先序遍历（递归）
中序遍历：对左子树中序遍历->根->对右子树中序遍历
后序遍历：对左子树后序遍历->对右子树后序遍历->根
'''
# 使用递归方式实现二叉树的深度优先遍历
def pre_order(self, root): # 由于需要递归调用本函数，故而必须要有一个形参
if root is None:
return
print(root.val, end=' ')
if root.left is not None:
self.pre_order(root.left) # 对左子树进行先序遍历
if root.right is not None:
self.pre_order(root.right)
def mid_order(self,root):
if root is None:
return
if self.root.left is not None:
self.mid_order(root.left)
print(root.val, end=' ') ##1 2 3 4 5 6 7 中序遍历
if self.root.right is not None:
self.mid_order(root.right)
def post_order(self, root):
if root is None:
return
if root.left is not None:
self.post_order(root.left)
if root.right is not None:
self.post_order(root.right)
print(root.val, end=' ')
if __name__ == '__main__':
A=[1, 2, 3, 4, 5, 6, 7]
solution=Solution()
result=solution.sortedArrayToBST(A)
bintree = BinaryTree(result)
retList=bintree.breathSearth()
# print(retList) #[4, 2, 6, 1, 3, 5, 7] # 广度遍历
# bintree.DFS(result) #1 3 2 5 7 6 4 #深度遍历 - 后序遍历
# print(bintree.DFS_STACK()) #[4, 2, 1, 3, 6, 5, 7] #深度遍历 - 前序遍历
# bintree.mid_order(result) #1 2 3 4 5 6 7 #深度遍历 - 中序遍历
print('#########先序遍历##########')
bintree.pre_order(result)
print()
print('#########中序遍历##########')
bintree.mid_order(result)
print()
print('#########后序遍历##########')
bintree.post_order(result)
结果为：
#########先序遍历##########
4 2 1 3 6 5 7
#########中序遍历##########
1 2 3 4 5 6 7
#########后序遍历##########
1 3 2 5 7 6 4
转载：https://blog.csdn.net/weixin_40446557/article/details/100928073
查看评论