package main
import "container/list"
// 二叉树深度优先遍历 递归 && 迭代
// ************递归遍历**********
// 前序遍历 NLR 根左右
func preorderRecur(root *TreeNode) []int {
var preorder func(node *TreeNode)
var res = []int{}
preorder = func(node *TreeNode) {
if node == nil {
return
}
res = append(res, node.Val)
preorder(node.Left)
preorder(node.Right)
}
preorder(root)
return res
}
// 中序遍历 LNR 左根右
func inorderRecur(root *TreeNode) []int {
var inorder func(node *TreeNode)
var res = []int{}
inorder = func(node *TreeNode) {
if node == nil {
return
}
inorder(node.Left)
res = append(res, node.Val)
inorder(node.Right)
}
inorder(root)
return res
}
// 后序遍历 LRN 左右根
func postorderRecur(root *TreeNode) []int {
var postorder func(node *TreeNode)
var res = []int{}
postorder = func(node *TreeNode) {
if node == nil {
return
}
postorder(node.Left)
postorder(node.Right)
res = append(res, node.Val)
}
postorder(root)
return res
}
// ************迭代遍历**********
// 前序遍历 NLR 根左右
func preorderIteration(root *TreeNode) []int {
if root == nil {
return nil
}
var stack = list.New()
stack.PushBack(root.Right)
stack.PushBack(root.Left)
res := []int{}
res = append(res, root.Val)
for stack.Len() > 0 {
e := stack.Back()
stack.Remove(e)
node := e.Value.(*TreeNode)
if node == nil {
continue
}
res = append(res, node.Val)
stack.PushBack(node.Right)
stack.PushBack(node.Left)
}
return res
}
// 后序遍历 LRN 左右根
func postorderIteration(root *TreeNode) []int {
if root == nil {
return nil
}
var stack = list.New()
stack.PushBack(root.Left)
stack.PushBack(root.Right)
var res = []int{}
res = append(res, root.Val)
for stack.Len() > 0 {
e := stack.Back()
stack.Remove(e)
node := e.Value.(*TreeNode)
if node == nil {
continue
}
res = append(res, node.Val)
stack.PushBack(node.Left)
stack.PushBack(node.Right)
}
for i := 0; i < len(res)/2; i++ {
res[i], res[len(res)-1-i] = res[len(res)-1-i], res[i]
}
return res
}
// 中序遍历 LNR 左根右
func inorderIteration(root *TreeNode) []int {
if root == nil {
return nil
}
var res = []int{}
var stack = list.New()
node := root
for node != nil {
stack.PushBack(node)
node = node.Left
}
for stack.Len() > 0 {
e := stack.Back()
stack.Remove(e)
node := e.Value.(*TreeNode)
res = append(res, node.Val)
node = node.Right
for node != nil {
stack.PushBack(node)
node = node.Left
}
}
return res
}
# 二叉树的深度优先遍历(DFS)
#********递归遍历**********#
# 前序 NLR-根左右 <递归 & 迭代> 遍历
def preorderRecur(root: TreeNode) -> [int]:
def preorder(root):
if root == None:
return []
res.append(root.val)
preorder(root.left)
preorder(root.right)
res = []
preorder(root)
return res
# 中序 LNR-左根右 <递归 & 迭代> 遍历
def inorderRecur(root: TreeNode) -> [int]:
def inorder(root):
if root == None:
return []
inorder(root.left)
res.append(root.val)
inorder(root.right)
res = []
inorder(root)
return res
# 后序 LRN-左右根 <递归 & 迭代> 遍历
def postorderRecur(root: TreeNode) -> [int]:
def postorder(root):
if root == None:
return []
postorder(root.left)
postorder(root.right)
res.append(root.val)
res = []
postorder(root)
return []
#********迭代遍历**********#
# 前序 NLR-根左右 <递归 & 迭代> 遍历
def preorderItration(root: TreeNode) -> [int]:
res = []
if root == None:
return res
stack = []
stack.append(root)
while stack:
node = stack.pop()
res.append(node.val) # 根节点最早加入res
# 右节点先入栈后出栈
if node.right:
stack.append(node.right)
# 左节点后入栈先出栈
if node.left:
stack.append(node.left)
return res
# 后序 LRN-左右根 <递归 & 迭代> 遍历
def postorderIteration(root: TreeNode) -> [int]:
if root == None:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
# 先处理中间节点
res.append(node.val)
# 左孩子先入栈后出栈
if node.left:
stack.append(node.left)
# 右孩子后入栈先出栈
if node.right:
stack.append(node.right)
# 由于res的添加顺序为 中右左,最后返回应该反转,即左右中
res = res[::-1]
return res
# 中序 LNR-左根右 <递归 & 迭代> 遍历
def inorderIteration(root: TreeNode) -> [int]:
if root == None:
return []
cur = root
stack = []
res = []
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
package binaryTree
import "container/list"
// 递归遍历
func levelOrderRecur(root *TreeNode) [][]int {
var levelOrder func(node *TreeNode, depth int)
var res [][]int
levelOrder = func(node *TreeNode, depth int) {
if node == nil {
return
}
if len(res) == depth {
res = append(res, []int{})
}
res[depth] = append(res[depth], node.Val)
if node.Left != nil {
levelOrder(node.Left, depth+1)
}
if node.Right != nil {
levelOrder(node.Right, depth+1)
}
}
levelOrder(root, 0)
return res
}
// 迭代遍历
func levelOrderiteration(root *TreeNode) [][]int {
var res = [][]int{}
if root == nil { // 空时返回
return res
}
queue := list.New() // 队列初始化
queue.PushBack(root)
var tmpArr []int
for queue.Len() > 0 {
length := queue.Len()
for i:=0;i<length;i++ { // 遍历当层的节点
node := queue.Remove(queue.Front()).(*TreeNode) // 当次节点
if node.Left != nil { // 节点的左节点入队
queue.PushBack(node.Left)
}
if node.Right != nil { // 节点的右节点入队
queue.PushBack(node.Right)
}
tmpArr = append(tmpArr, node.Val) // 节点值加入结果集
}
res = append(res, tmpArr)
tmpArr = []int{}
}
return res
}
# 0102.二叉树的层序遍历
class Solution:
def levelOrder(self, root: TreeNode) -> [[int]]:
"""
迭代法:双端队列,每次把单层的节点遍历出队列,另外将对应的左右节点加入队列
:param root:
:return:
"""
results = []
if not root:
return results
from collections import deque
queue = deque([root]) # 初始化队列
while queue:
size = len(queue) # 遍历队列单层长度
res = [] # 每次遍历时初始化加入结果集中的列表
for _ in range(size):
cur = queue.popleft() # 通过size控制遍历次数
res.append(cur.val) # 加入结果集中
if cur.left: # 添加当前pop节点的左节点进入队列
queue.append(cur.left)
if cur.right: # 添加当前pop节点的右节点进入队列
queue.append(cur.right)
results.append(res) # 当层中的所有节点的值放入list中
return results
def levelOrderRecur(self, root: TreeNode) -> [[int]]:
"""
递归法,
:param root:
:return:
"""
res = []
def levelOrder(node, index):
if not node: # 空,返空
return []
if len(res) < index: # 开始当前depth
res.append([])
res[index-1].append(node.val) # 当前层加入节点值到结果集
if node.left: # 当前节点有左节点,继续递归,同时层数加1
levelOrder(node.left, index+1)
if node.right: # 当前节点有右节点,继续递归,同时层数加1
levelOrder(node.right, index+1)
levelOrder(root, 1) # 1层开始递归
return res
posted on 2021-11-11 23:47 进击的davis 阅读(127) 评论(0) 编辑 收藏 举报