DFS的实现实际利用的结构是 stack（先进后出）
144. 二叉树的前序遍历
image.png
方法1--递归
递归:就是依次输出根,左,右,递归下去，有两种写法，一种是更简单的，一种稍微复杂。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def helper(root):
if not root:
return
res.append(root.val)
helper(root.left)
helper(root.right)
helper(root)
return res
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
ans=[]
if not root:
return []
return [root.val]+self.preorderTraversal(root.left)+self.preorderTraversal(root.right) if root else []
方法2--迭代
迭代:使用栈来完成,我们先将根节点放入栈中,然后将其弹出,依次将该弹出的节点的右节点,和左节点,注意顺序,是右,左,为什么?因为栈是先入先出的,我们要先输出右节点,所以让它先进栈.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
if not root:
return res
stack = [root]
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
145. 二叉树的后序遍历
image.png
方法1--递归
递归:同理,顺序:左,右,根
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def helper(root):
if not root:
return
helper(root.left)
helper(root.right)
res.append(root.val)
helper(root)
return res
# 递归写法
#class Solution:
# def postorderTraversal(self, root: TreeNode) -> List[int]:
# if not root:return []
# return self.postorderTraversal(root.left)+self.postorderTraversal(root.right)+[root.val] if root else []
方法2--迭代
迭代:这就很上面的先序一样,我们可以改变入栈的顺序,刚才先序是从右到左,我们这次从左到右,最后得到的结果取逆
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
res = []
if not root:
return res
stack = [root]
while stack:
node = stack.pop()
if node.left :
stack.append(node.left)
if node.right:
stack.append(node.right)
res.append(node.val)
return res[::-1]
94. 二叉树的中序遍历
递归:顺序,左右根
非递归:这次我们用一个指针模拟过程
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
def helper(root):
if not root:
return
helper(root.left)
res.append(root.val)
helper(root.right)
helper(root)
return res
# 递归写法
#class Solution:
# def inorderTraversal(self, root: TreeNode) -> List[int]:
# if not root:return []
# return self.inorderTraversal(root.left)+[root.val]+self.inorderTraversal(root.right) if root else []
代,首先先达到root的最左端None的位置，用stack记录经过所有节点，然后开始出栈，得到左端叶子的值，并加入列表res，接着访问叶子的right，若为空，stack继续出栈，得到叶子的上一个节点，以此类推，最后stack为空，并且此时达到最右端叶子
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
if not root:
return res
stack = []
cur = root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
网友评论