二叉树的介绍:二叉树-leetcode
前序:
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root is None:
return []
stack = [root]
res = []
while stack :
temp = stack.pop()
res.append(temp.val)
if temp.right:
stack.append(temp.right)
if temp.left:
stack.append(temp.left)
return res
中序:
参考:二叉树的中序遍历
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root is None:
return []
res=[]
stack = []
temp = root
while stack or temp:
while temp:
stack.append(temp)
temp=temp.left
temp = stack.pop()
res.append(temp.val)
temp=temp.right
return res
后序:
参考:刷题系列 - Python用非递归实现二叉树后续遍历
想了半天没想出来非递归的思路…写出来的总是有错,然后参考了链接↑的代码……
思路:从左开始遍历并放入栈,读取没有下级节点的节点值,然后把该节点推出栈,并删除和上级节点关联;然后替换栈中最上的点,并去遍历右边子节点;直到栈为空,遍历结束。
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
traversalList = []
nodeList = []
if root != None:
nodeList.append(root)
while nodeList != []:
if nodeList[-1].left != None:
nodeList.append(nodeList[-1].left )
elif nodeList[-1].right != None:
nodeList.append(nodeList[-1].right)
else:
traversalList.append(nodeList[-1].val)
currentNode = nodeList.pop()
if nodeList != []:
if nodeList[-1].right == currentNode:
nodeList[-1].right = None
elif nodeList[-1].left == currentNode:
nodeList[-1].left = None
return traversalList
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)