【Leetcode】树的遍历（前、中、后、层序）
2020-07-20 本文已影响0人
李白开水
前序遍历
144. 二叉树的前序遍历
递归：
- 返回的结果为res数组，遇到一个点，如果这个点存在，就把这个点的值append到res中，如果不存在，返回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]:
return self.helper(root, [])
def helper(self, node, res):
if not node:
return res
res.append(node.val)
self.helper(node.left, res)
self.helper(node.right, res)
return res
迭代：
- 注意left和right的顺序
- 因为pop是pop出数组的最后一个元素，所以要把right节点压在栈底，把left节点放在后面，这样才能先遍历left
# 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]:
if not root:
return []
stack = [root]
res = []
while stack:
cur = stack.pop()
res.append(cur.val)
if cur.right:
stack.append(cur.right)
if cur.left:
stack.append(cur.left)
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]:
if not root:
return []
stack = [root]
res = []
while stack:
cur = stack.pop(0)
res.append(cur.val)
if cur.right:
stack = [cur.right] + stack
if cur.left:
stack = [cur.left] + stack
return res
589. N叉树的前序遍历
递归：
- 节点的children是list
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def preorder(self, root: 'Node') -> List[int]:
return self.helper(root, [])
def helper(self, node, res):
if not node:
return res
res.append(node.val)
for i in node.children:
self.helper(i,res)
return res
迭代：
- 每个节点的children是一个list，所以list和list之间直接+
- 因为pop是pop出最后一个元素，为了先遍历左边的节点，children的list要逆序
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def preorder(self, root: 'Node') -> List[int]:
if not root:
return []
stack = [root]
res = []
while stack:
cur = stack.pop()
res.append(cur.val)
if cur.children:
stack += cur.children[::-1]
return res
中序遍历
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: TreeNode) -> List[int]:
return self.helper(root, [])
def helper(self, node, res):
if not node:
return res
if node.left:
self.helper(node.left, res)
res.append(node.val)
if node.right:
self.helper(node.right, res)
return res
迭代：
- 如果当前节点不为空，把当前节点加到栈中
- 如果当前节点为空，把栈中的最后一个节点pop出来，把这个节点的值加到结果集中，把这个节点的右节点赋给当前节点
# 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: TreeNode) -> List[int]:
res = []
stack = []
cur = root
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
后序遍历
145. 二叉树的后序遍历
递归：
# 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]:
return self.helper(root, [])
def helper(self, node, res):
if not node:
return res
if node.left:
self.helper(node.left, res)
if node.right:
self.helper(node.right, res)
res.append(node.val)
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 postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = [root]
stack2 = []
while stack:
node = stack.pop()
stack2.append(node)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return [i.val for i in stack2[::-1] ]
或:
# 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]:
if not root:
return []
tmp = [root]
res = []
while tmp:
cur = tmp.pop()
res.append(cur.val)
if cur.left:
tmp.append(cur.left)
if cur.right:
tmp.append(cur.right)
return res[::-1]
590. N叉树的后序遍历
递归：
- 如果有孩子，先遍历孩子
- 如果没有孩子了，把当前的节点的值加到res中
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def postorder(self, root: 'Node') -> List[int]:
return self.helper(root, [])
def helper(self, node, res):
if not node:
return res
if node.children:
for i in node.children:
self.helper(i, res)
res.append(node.val)
return res
层序遍历
102. 二叉树的层序遍历
- 一层一层遍历
- 当前这一层的节点在cur中，遍历cur，把下一层的所有节点append到nex中，把当前这一层所有节点的val作为一个数组append到结果集中，再把下一层要遍历的所有节点的数组赋给当前节点的数组
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
res = []
cur = [root]
while cur:
tmp = []
nex = []
for i in cur:
tmp.append(i.val)
if i.left:
nex.append(i.left)
if i.right:
nex.append(i.right)
cur = nex
res.append(tmp)
return res
429. N叉树的层序遍历
- 和二叉树的层序遍历一样，只不过N叉树节点的children是一个list
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
if not root:
return []
res = []
cur = [root]
while cur:
tmp = []
nex = []
for i in cur:
tmp.append(i.val)
if i.children:
nex += i.children
cur = nex
res.append(tmp)
return res
