徐旭 的个人博客

二叉树的遍历(递归,迭代)

image.png

图片来自 leetcode

  • 深度优先遍历(dfs)
    • 前序遍历
    • 中序遍历
    • 后序遍历
  • 广度优先遍历(bfs)

前序遍历

import "github.com/Allenxuxu/toolkit/stack"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func preorderTraversal(root *TreeNode) []int {
	var ret []int
	helperPreOrder(root, &ret)
	return ret
}

func helperPreOrder(root *TreeNode, data *[]int) {
	if root == nil {
		return
	}
	*data = append(*data, root.Val)
	helperPreOrder(root.Left, data)
	helperPreOrder(root.Right, data)
}

func preorderTraversal1(root *TreeNode) []int {
	if root == nil {
		return nil
	}

	var ret []int
	s := stack.New()
	s.Push(root)

	for s.Len() > 0 {
		node := s.Pop().(*TreeNode)
		ret = append(ret, node.Val)

		if node.Right != nil {
			s.Push(node.Right)
		}
		if node.Left != nil {
			s.Push(node.Left)
		}
	}

	return ret
}

func preorderTraversal2(root *TreeNode) []int {
	var ret []int
	s := stack.New()

	for root != nil || s.Len() > 0 {
		for root != nil {
			s.Push(root)
			ret = append(ret, root.Val)
			root = root.Left
		}

		root = s.Pop().(*TreeNode)
		root = root.Right
	}

	return ret
}

中序遍历


import "github.com/Allenxuxu/toolkit/stack"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func inorderTraversal(root *TreeNode) []int {
	var ret []int
	helper(root, &ret)
	return ret
}

func helper(root *TreeNode, data *[]int) {
	if root == nil {
		return
	}
	helper(root.Left, data)
	*data = append(*data, root.Val)
	helper(root.Right, data)
}

func inorderTraversal2(root *TreeNode) []int {
	var ret []int
	s := stack.New()

	for root != nil || s.Len() > 0 {
		for root != nil {
			s.Push(root)
			root = root.Left
		}

		root = s.Pop().(*TreeNode)
		ret = append(ret, root.Val)

		root = root.Right
	}

	return ret
}

后序遍历


import (
	"github.com/Allenxuxu/toolkit/stack"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func postorderTraversal(root *TreeNode) []int {
	var ret []int
	helperPostOrder(root, &ret)
	return ret
}

func helperPostOrder(root *TreeNode, data *[]int) {
	if root == nil {
		return
	}
	helperPostOrder(root.Left, data)
	helperPostOrder(root.Right, data)
	*data = append(*data, root.Val)
}

func postorderTraversal1(root *TreeNode) []int {
	if root == nil {
		return nil
	}

	var ret []int
	s := stack.New()
	s.Push(root)

	for s.Len() > 0 {
		node := s.Pop().(*TreeNode)
		ret = append(ret, node.Val)

		if node.Left != nil {
			s.Push(node.Left)
		}
		if node.Right != nil {
			s.Push(node.Right)
		}
	}

	reversal(ret)
	return ret
}

func reversal(a []int) {
	for i := 0; i < len(a)/2; i++ {
		a[i], a[len(a)-1-i] = a[len(a)-1-i], a[i]
	}
}

func postorderTraversal2(root *TreeNode) []int {
	var ret []int
	s := stack.New()
	var last *TreeNode
	for root != nil || s.Len() > 0 {
		for root != nil {
			s.Push(root)
			root = root.Left
		}

		// peek
		root = s.Pop().(*TreeNode)
		s.Push(root)

		if root.Right == nil || root.Right == last {
			ret = append(ret, root.Val)
			s.Pop()

			last = root
			root = nil
		} else {
			root = root.Right
		}
	}
	return ret
}


标题:二叉树的遍历(递归,迭代)
作者:Allenxuxu
地址:https://mogutou.xyz/articles/2020/04/26/1587906162356.html
Github: https://github.com/Allenxuxu
转载请注明出处

0 浏览