遍历(LC144,LC145,LC94"/>
6.2二叉树的迭代遍历(LC144,LC145,LC94
递归的实现原理:
每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中,然后递归返回的时候,从栈顶弹出上一次递归的各项参数,所以这就是递归为什么可以返回上一层位置的原因。
所以,使用栈也可以实现二叉树的前后中序遍历
然而,使用迭代法实现先中后序遍历,很难写出统一的代码(中序和先序后序很不一样),不像是递归法,实现了其中的一种遍历方式,其他两种只要稍稍改一下节点顺序就可以了。代码随想录 (programmercarl)
中序和先序后序很不一样:
因为中序遍历是“左中右”,但是访问时肯定先访问根节点,而根节点又不是中序遍历第一个输出的节点。
接下来学习迭代遍历的统一写法
算法(以中序遍历(LVR)为例):
由于栈“先入后出”,访问节点的顺序应为“RVL”:当我们遇到一个节点时,我们首先将其右子节点(如果存在)推入栈中。然后,我们将该节点自身推入栈中,并在其后面推入一个空节点作为标记。最后,我们将其左子节点(如果存在)推入栈中。
加入空节点,以标记已经访问过、但尚未处理的中节点。
举个例子理解一下:
5 / \ 4 6 / \ 1 2
中序遍历(LVR):[1,4,2,5,6]
使用加入空节点的代码来执行中序遍历,访问节点的顺序为“RVL”,以下为入栈操作:
- R:将根节点的右子节点6推入栈中。//[6]
- V:推入根节点5。//[6,5]
- 推入空节点以标记根节点5尚未被处理。//[6,5,None]
- R:上一个节点为空,此时访问节点5的左子树的右节点2//[6,5,None,2]
- V:推入中节点4。//[6,5,None,2,4]
- 推入空节点以标记节点4尚未被处理。//[6,5,None,2,4,None]
- R:上一个节点为空,此时访问节点4的左子树的右节点,发现为空
- V:推入中节点1。//[6,5,None,2,4,None,1]
最后pop(cur!=None):[1,4,2,5,6]
调试过程(中序遍历):
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
#LVR
class Solution:def inorderTraversal(self, root: TreeNode) -> List[int]:res = []if root == None:return reselse:stack = [root]#当栈为空时,循环终止while stack:node = stack.pop()if node:if node.right != None:stack.append(node.right)stack.append(node.val)stack.append(None)if node.left != None:stack.append(node.left)else:#只有遇到空节点的时候,才将下一个节点放进resnode = stack.pop()#把None pop出去,然后往res中送入stack中的noderes.append(node.val)return res
原因:我压入的是节点的值,而不是节点,所以pop的时候也是pop的节点的值,而node.val没有node.val.val了,所以要把stack.append(node.val),改成stack.append(node)
节点对象和节点值之间的区别。
在二叉树中,每个节点都有一个值和指向左右子节点的指针。节点对象是一个包含节点值和指针的数据结构,它通常由程序员定义并实现。节点值是节点对象的一个属性,用于存储节点所代表的值。
在代码中,我们使用节点对象来表示二叉树的节点,并使用节点对象的属性来访问节点的值和子节点。当我们将节点对象添加到栈中时,我们可以通过访问节点对象的属性来获取节点的值和子节点。
为什么遇到空节点的时候,放进res的是空节点的下一个节点?
为什么遇到空节点时,将下一个节点放入`res
`,而不是空节点本身,原因是在代码中,我们将空节点`None
`作为一个标记,表示当前节点已经处理完毕,需要处理栈中的下一个节点。因此,我们实际上是将下一个节点添加到`res
`中,而不是空节点本身。
正确代码:
中序遍历(LVR):
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
#LVR
class Solution:def inorderTraversal(self, root: TreeNode) -> List[int]:res = []if root == None:return reselse:stack = [root]#当栈为空时,循环终止while stack:node = stack.pop()if node:if node.right != None:stack.append(node.right)stack.append(node)stack.append(None)if node.left != None:stack.append(node.left)else:#只有遇到空节点的时候,才将下一个节点放进resnode = stack.pop()#把None pop出去,然后往res中送入stack中的noderes.append(node.val)return res
前序遍历(VLR):
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
#VLR
class Solution:def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:res = []if root == None:return reselse:stack = [root]#当栈为空时,循环终止while stack:node = stack.pop()if node:if node.right != None:stack.append(node.right)if node.left != None:stack.append(node.left)stack.append(node)stack.append(None)else:#只有遇到空节点的时候,才将下一个节点放进resnode = stack.pop()#把None pop出去,然后往res中送入stack中的noderes.append(node.val)return res
后序遍历(LRV):
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:res = []if root == None:return reselse:stack = [root]#当栈为空时,循环终止while stack:node = stack.pop()if node:stack.append(node)#中stack.append(None)if node.right != None:#右stack.append(node.right)if node.left != None:#左stack.append(node.left)else:#只有遇到空节点的时候,才将下一个节点放进resnode = stack.pop()#把None pop出去,然后往res中送入stack中的noderes.append(node.val)return res
更多推荐
6.2二叉树的迭代遍历(LC144,LC145,LC94
发布评论