本文主要是介绍二叉树的前序、中序、后序遍历（python递归），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
先序遍历
1、Binary Tree Preorder Traversal---leetcode144
#coding:utf-8
class Solution:#根左右def preorderTraversal(self, root):if not root:return []return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)# 给定二叉树的前序遍历和中序遍历，获得该二叉树def getBSTwithPreTin(self, pre, tin):if len(pre)==0 | len(tin)==0:return Noneroot = treeNode(pre[0])for order,item in enumerate(tin):if root .val == item:root.left = self.getBSTwithPreTin(pre[1:order+1], tin[:order])root.right = self.getBSTwithPreTin(pre[order+1:], tin[order+1:])return rootclass treeNode:def __init__(self, x):self.left = Noneself.right = Noneself.val = xif __name__ == '__main__':flag = "printTreeNode"solution = Solution()preorder_seq = [1, 2, 4, 7, 3, 5, 6, 8]middleorder_seq = [4, 7, 2, 1, 5, 3, 8, 6]treeRoot1 = solution.getBSTwithPreTin(preorder_seq, middleorder_seq)if flag == "printTreeNode":newArray = solution.preorderTraversal(treeRoot1)print(newArray)2、Binary Tree Inorder Traversal---leetcode94
#coding:utf-8
class Solution:#左根右def inorderTraversal(self, root):if not root:return []return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)# 给定二叉树的前序遍历和中序遍历，获得该二叉树def getBSTwithPreTin(self, pre, tin):if len(pre)==0 | len(tin)==0:return Noneroot = treeNode(pre[0])for order,item in enumerate(tin):if root .val == item:root.left = self.getBSTwithPreTin(pre[1:order+1], tin[:order])root.right = self.getBSTwithPreTin(pre[order+1:], tin[order+1:])return rootclass treeNode:def __init__(self, x):self.left = Noneself.right = Noneself.val = xif __name__ == '__main__':flag = "printTreeNode"solution = Solution()preorder_seq = [1, 2, 4, 7, 3, 5, 6, 8]middleorder_seq = [4, 7, 2, 1, 5, 3, 8, 6]treeRoot1 = solution.getBSTwithPreTin(preorder_seq, middleorder_seq)if flag == "printTreeNode":newArray = solution.inorderTraversal(treeRoot1)print(newArray)3、Binary Tree Posorder Traversal---leetcode145
#coding:utf-8
class Solution:#左右根def postorderTraversal(self, root):if not root:return []return self.postorderTraversal(root.left) + self.postorderTraversal(root.right)+[root.val]# 给定二叉树的前序遍历和中序遍历，获得该二叉树def getBSTwithPreTin(self, pre, tin):if len(pre)==0 | len(tin)==0:return Noneroot = treeNode(pre[0])for order,item in enumerate(tin):if root .val == item:root.left = self.getBSTwithPreTin(pre[1:order+1], tin[:order])root.right = self.getBSTwithPreTin(pre[order+1:], tin[order+1:])return rootclass treeNode:def __init__(self, x):self.left = Noneself.right = Noneself.val = xif __name__ == '__main__':flag = "printTreeNode"solution = Solution()preorder_seq = [1, 2, 4, 7, 3, 5, 6, 8]middleorder_seq = [4, 7, 2, 1, 5, 3, 8, 6]treeRoot1 = solution.getBSTwithPreTin(preorder_seq, middleorder_seq)if flag == "printTreeNode":newArray = solution.postorderTraversal(treeRoot1)print(newArray)
这篇关于二叉树的前序、中序、后序遍历（python递归）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
