主要核心是遍历思路：
前序：根左右
中序：左根右
后序：左右根
针对每一颗树，每一颗树的左右子树都是如此遍历
1、递归遍历
# classTreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
#
# @paramroot TreeNode类 the root of binary tree
# @returnint整型二维数组
#
classSolution:
def threeOrders(self , root ):
# write code here
def preorder(root):
ifnot root:
return[]
d=[root]
l=[]
whiled:
tmp=d.pop()
l.append(tmp.val)
iftmp.right:
d.append(tmp.right)
iftmp.left:
d.append(tmp.left)
returnl
def inorder(root):
ifnot root:
return[]
stack = []
l=[]
whilestack or root:
ifroot:
stack.append(root)
root = root.left
else:
root = stack.pop()
l.append(root.val)
root = root.right
returnl
def postorder(root):
ifnot root:
return[]
returnpostorder(root.left)+postorder(root.right)+[root.val]
res=[]
res.append(preorder(root))
res.append(inorder(root))
res.append(postorder(root))
returnres
2、非递归
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
#
# @param root TreeNode类 the root of binary tree
# @return int整型二维数组
#
class Solution:
def threeOrders(self , root ):
# write code here
def preorder(root):
if not root:
return []
d=[root]
l=[]
while d:
tmp=d.pop()
l.append(tmp.val)
if tmp.right:
d.append(tmp.right)
if tmp.left:
d.append(tmp.left)
return l
def inorder(root):
if not root:
return []
stack = []
pos=root
l=[]
while len(stack) > 0 or pos:
if pos:
stack.append(pos)
pos = pos.left
else:
pos = stack.pop()
l.append(pos.val)
pos = pos.right
return l
def postorder(root):
if not root:
return []
stack=[root]
stack2=[]
l=[]
while len(stack) > 0:
tmp=stack.pop()
stack2.append(tmp)
if tmp.left:
stack.append(tmp.left)
if tmp.right:
stack.append(tmp.right)
while len(stack2) > 0:
l.append((stack2.pop().val))
return l
res=[]
res.append(preorder(root))
res.append(inorder(root))
res.append(postorder(root))
return res
参考资料：
1、Python 实现二叉树的前序、中序、后序、层次遍历（递归和非递归版本）
https://blog.csdn.net/m0_37324740/article/details/82763901
网友评论