今日day11：三种二叉树的遍历方式
1 首先是递归遍历。需要首先搞懂前序中序后序遍历的意思，即以根root的位置为准
前序即根左右 中序即左根右 后序即左右根
递归则是指在函数中循环调用自身直至跳出递归条件
python实现
原理仅有遍历顺序的变化为区别，首先声明一个空res数组用以存放数值，遍历即依次获取树各节点的值，递归的条件是root仍然存在，由于二叉树的各子树仍然满足二叉树之定义因此当访问到根时就将值送入res数组，再调整root去找左右节点，而左右节点为根时仍然满足二叉树定义即实现了遍历
# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def dfs(root):
if root:
res.append(root.val)
dfs(root.left)
dfs(root.right)
dfs(root)
return res
"中序"
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def dfs(root):
if root:
dfs(root.left)
res.append(root.val)
dfs(root.right)
dfs(root)
return res
"后序"
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def dfs(root):
if root:
dfs(root.left)
dfs(root.right)
res.append(root.val)
dfs(root)
return res
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
//前序
func preorderTraversal(root *TreeNode) []int {
var dfs func(node *TreeNode)
var res []int
dfs = func(node *TreeNode){
if node == nil {
return
}
res = append(res,node.Val)
dfs(node.Left)
dfs(node.Right)
}
dfs(root)
return res
}
//中序
func inorderTraversal(root *TreeNode) []int {
var dfs func(node *TreeNode)
var res []int
dfs = func(node *TreeNode){
if node == nil{
return
}
dfs(node.Left)
res = append(res,node.Val)
dfs(node.Right)
}
dfs(root)
return res
}
//后序
func postorderTraversal(root *TreeNode) []int {
var dfs func(node *TreeNode)
var res []int
dfs = func(node *TreeNode){
if node == nil {
return
}
dfs(node.Left)
dfs(node.Right)
res = append(res,node.Val)
}
dfs(root)
return res
}
2 其次是迭代遍历，该法旨在使用栈作为暂存值的结构并根据遍历顺序适当调整
"先使用数组存储root，一旦其存在就将值弹出即先进后出，再将其追加至result中，然后由于栈是先进先出，所以先右后左"
"先序"
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
stack = [root]
result =[]
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
"中序"
"先不要将root放入stack中，使用指针指向root以供操作，该方法旨在先将根加入栈中再访问其左节点然后先出左节点后此时又指向右节点，再令其找右节点如上操作，则完成了中序"
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
stack = []
result = []
cur = root
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
result.append(cur.val)
cur = cur.right
return result
"后序"
"基本操作如前序，但考虑到栈的先进先出，我们将其位置调整为根右左并反转，这样就成为了左右根"
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
stack = [root]
result = []
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result[::-1]
//先序
//借助双端链表list及其中的函数
func preorderTraversal(root *TreeNode) []int {
ans := []int{}
if root == nil {
return ans
}
st:=list.New()
//尾插root
st.PushBack(root)
for st.Len() > 0{
//弹出末尾节点并声明其类型为treenode
node := st.Remove(st.Back()).(*TreeNode)
ans = append(ans,node.Val)
if node.Right != nil{
st.PushBack(node.Right)
}
if node.Left != nil {
st.PushBack(node.Left)
}
}
return ans
}
//中序
func inorderTraversal(root *TreeNode) []int {
ans :=[]int{}
if root == nil{
return ans
}
st := list.New()
cur := root
for cur != nil || st.Len() > 0 {
if cur!=nil{
st.PushBack(cur)
cur = cur.Left
}else{
cur = st.Remove(st.Back()).(*TreeNode)
ans = append(ans,cur.Val)
cur = cur.Right
}
}
return ans
}
//后序
func postorderTraversal(root *TreeNode) []int {
ans := []int{}
if root == nil {
return ans
}
st := list.New()
st.PushBack(root)
for st.Len() >0 {
node := st.Remove(st.Back()).(*TreeNode)
ans = append(ans,node.Val)
if node.Left != nil{
st.PushBack(node.Left)
}
if node.Right != nil{
st.PushBack(node.Right)
}
}
reverse(ans)
return ans
}
func reverse(a []int) {
l,r := 0,len(a)-1
for l < r {
a[l],a[r] = a[r],a[l]
l,r = l+1,r-1
}
}
3 最后是统一迭代法：
"前序"
"类似使用栈进行遍历并考虑出栈顺序，但它把元素入结果集的操作统一进行，先完成元素的顺序寻找"
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
st = []
if root:
st.append(root)
while st:
node = st.pop()
if node != None:
if node.right:
st.append(node.right)
if node.left:
st.append(node.left)
st.append(node)
st.append(None)
else:
node = st.pop()
result.append(node.val)
return result
"中序"
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
st = []
if root:
st.append(root)
while st:
node = st.pop()
if node != None:
if node.right:
st.append(node.right)
st.append(node)
st.append(None)
if node.left:
st.append(node.left)
else:
node = st.pop()
result.append(node.val)
return result
"后序"
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
st = []
if root:
st.append(root)
while st:
node = st.pop()
if node != None:
st.append(node)
st.append(None)
if node.right:
st.append(node.right)
if node.left:
st.append(node.left)
else:
node = st.pop()
result.append(node.val)
return result
//前序
func preorderTraversal(root *TreeNode) []int {
if root == nil {
return nil
}
var stack = list.New()
res:=[]int{}
stack.PushBack(root)
var node *TreeNode
for stack.Len() > 0{
e := stack.Back()
stack.Remove(e)//弹出元素
if e.Value == nil { //如果为空，则表明需要处理中间节点
e = stack.Back()//弹出元素
stack.Remove(e)//删除中间节点
node = e.Value.(*TreeNode)
res = append(res,node.Val)//将中间节点加入到结果集合中
continue //继续弹出下一个
}
node = e.Value.(*TreeNode)
if node.Right != nil {
stack.PushBack(node.Right)
}
if node.Left !=nil {
stack.PushBack(node.Left)
}
stack.PushBack(node)
stack.PushBack(nil)
}
return res
}
//中序
func inorderTraversal(root *TreeNode) []int {
if root == nil {
return nil
}
stack := list.New()
res :=[]int{}
stack.PushBack(root)
var node *TreeNode
for stack.Len() >0 {
e := stack.Back()
stack.Remove(e)
if e.Value == nil {
e = stack.Back()
stack.Remove(e)
node = e.Value.(*TreeNode)
res = append(res,node.Val)
continue
}
node = e.Value.(*TreeNode)
if node.Right!=nil {
stack.PushBack(node.Right)
}
stack.PushBack(node)
stack.PushBack(nil)
if node.Left != nil{
stack.PushBack(node.Left)
}
}
return res
}
//后序
func postorderTraversal(root *TreeNode) []int {
if root == nil {
return nil
}
var stack = list.New()
res :=[]int{}
stack.PushBack(root)
var node *TreeNode
for stack.Len() >0 {
e := stack.Back()
stack.Remove(e)
if e.Value == nil {
e = stack.Back()
stack.Remove(e)
node = e.Value.(*TreeNode)
res=append(res,node.Val)
continue
}
node = e.Value.(*TreeNode)
stack.PushBack(node)
stack.PushBack(nil)
if node.Right!=nil{
stack.PushBack(node.Right)
}
if node.Left!= nil {
stack.PushBack(node.Left)
}
}
return res
}