基于递归的遍历

先序遍历

先序遍历方式1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//✅代码
func PreorderTraverse(root *TreeNode) []int {
if root == nil {
return nil
}

var ret []int
ret = append(ret, root.Val)
if root.Left != nil {
ret = append(ret, PreorderTraverse(root.Left)...)
}

if root.Right != nil {
ret = append(ret, PreorderTraverse(root.Right)...)
}

return ret
}

先序遍历方式2

1
2
3
4
5
6
7
8
9
10
11
12
func PreorderTraverseII(root *TreeNode) []int {
if root == nil {
return nil
}

var ret []int
ret = append(ret, root.Val)
ret = append(ret, PreorderTraverse(root.Left)...)
ret = append(ret, PreorderTraverse(root.Right)...)

return ret
}

先序遍历错误方式

错误方式

1
2
3
4
5
6
7
8
9
10
func PreorderTraverseIII(root *TreeNode) []int {
if root == nil {
return nil
}

var ret []int
ret = append(ret, root.Val, PreorderTraverseIII(root.Left)..., PreorderTraverseIII(root.Right)...)

return ret
}

中序遍历

中序遍历

1
2
3
4
5
6
7
8
9
10
11
func InorderTraverse(root *TreeNode) []int {
if root == nil {
return nil
}

var ret []int
ret = append(ret, InorderTraverse(root.Left)...)
ret = append(ret, root.Val)
ret = append(ret, InorderTraverse(root.Right)...)
return ret
}

后序遍历

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
func PostorderTraverse(root *TreeNode) []int {
if root == nil {
return nil
}

var ret []int
ret = append(ret, PostorderTraverse(root.Left)...)
ret = append(ret, PostorderTraverse(root.Right)...)
ret = append(ret, root.Val)

return ret
}

基于非递归的遍历

先序遍历

  1. 申请一个新的栈,记为stack,然后将头结点压入到stack中
  2. 从stack中弹出栈顶结点,记为cur,然后打印cur结点的值,再将cur结点的右孩子(不为空)压入到栈中,最后将左孩子(不为空)压入到stack中
  3. 不断重复步骤2,直到stack为空,全部过程结束

非递归实现二叉树的先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//✅
//思路:使用栈来求解,初始化的时候若根不为空,则将根加入到栈中,
//之后,每次遍历到一个节点将值加入到结果中并弹出,然后将右子树加入到栈中,之后将左子树加入到栈中
func PreorderTraverseNoRecursion(root *TreeNode) []int {
if root == nil {
return nil
}
var ret []int
stack := []*TreeNode{root}

for len(stack) != 0 {
//首先从栈中弹出一个节点
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]

//将当前节点的值加入到我们要返回的结果中
ret = append(ret, node.Val)

//将当前节点的右节点加入到栈中
if node.Right != nil {
stack = append(stack, node.Right)
}

//将当前节点的左节点加入到栈中
if node.Left != nil {
stack = append(stack, node.Left)
}
}
return ret
}

中序遍历

  1. 申请一个新栈,记为stack。初始时,令变量cur = head
  2. 先把cur节点压入栈中,对以cur节点为头节点的整颗子树来说,依次把左边界压入到栈中,即不停地令cur = cur.Left,然后重复步骤3
  3. 不断重复步骤2,直到发现cur为空,此时从stack中弹出一个节点,记为node,打印node的值,并且让cur = node.right,然后继续重复步骤2。
  4. 当stack为空且cur为空,整个过程停止。

非递归实现二叉树的中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//✅
func InorderTraverseNoRecursion(root *TreeNode) []int {
//如果为空,直接返回
if root == nil {
return nil
}

var ret []int
var stack []*TreeNode
cur := root

for cur != nil || len(stack) != 0 {
if cur != nil {
//说明当前节点是第一次遍历,直接加入到栈中
stack = append(stack, cur)
//之后移动到该节点的左子树节点
cur = cur.Left
} else {
//首先从栈中弹出一个节点
cur = stack[len(stack)-1]
stack = stack[:len(stack)-1]
//将当前节点的值加入到结果中
ret = append(ret, cur.Val)
//之后移动到当前节点的右节点
cur = cur.Right
}
}

return ret
}

后序遍历

第一种方式:

先介绍用两个栈实现后序遍历的过程,具体过程如下:

1.申请一个栈,记为s1,然后将头节点head压入s1中。

2.从s1中弹出的节点记为cur,然后依次将cur的左孩子和右孩子压入s1中。

3.在整个过程中,每一个从s1中弹出的节点都放进s2中。

4.不断重复步骤2和步骤3,直到s1为空,过程停止。

5.从s2中依次弹出节点并打印,打印的顺序就是后序遍历的顺序。”

通过如上过程我们知道,每棵子树的头节点都最先从s1中弹出,然后把该节点的孩子节点按照先左再右的顺序压入s1,那么从s1弹出的顺序就是先右再左,所以从s1中弹出的顺序就是中、右、左。然后,s2重新收集的过程就是把s1的弹出顺序逆序,所以s2从栈顶到栈底的顺序就变成了左、右、中。

非递归实现二叉树的后序遍历方式1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//✅
//方法一:使用两个栈实现二叉树的非递归后序遍历
func PostorderTraverseNoRecursion(root *TreeNode) []int {
if root == nil {
return nil
}

var ret []int
var stack2 []*TreeNode

//首先我们将root加入到stack1中
stack1 := []*TreeNode{root}

//如果stack1不为空
for len(stack1) != 0 {
cur := stack1[len(stack1)-1]
//将当前节点从栈1移除并且将当前节点加入到栈2
stack1 = stack1[:len(stack1)-1]

//将当前节点的左右子节点分别加入到栈1

//注意点1:这里有可能左右子节点有可能为空
if cur.Left != nil {
stack1 = append(stack1, cur.Left)
}

if cur.Right != nil {
stack1 = append(stack1, cur.Right)
}

//之后将当前节点加入到栈2中
stack2 = append(stack2, cur)
}

//最后我们从stack2弹出的顺序就是我们后序遍历得到的结果
for len(stack2) != 0 {
node := stack2[len(stack2)-1]
stack2 = stack2[:len(stack2)-1]
ret = append(ret, node.Val)
}

return ret
}
第二种方式:

最后介绍只用一个栈实现后序遍历的过程,具体过程如下:

1.申请一个栈,记为stack,将头节点压入stack,同时设置两个变量h和c。在整个流程中,h代表最近一次弹出并打印的节点,c代表”

摘录来自: 左程云. “程序员代码面试指南:IT名企算法与数据结构题目最优解。” Apple Books.

“stack的栈顶节点,初始时h为头节点,c为null。

2.每次令c等于当前stack的栈顶节点,但是不从stack中弹出,此时分以下三种情况。

①:如果c的左孩子不为null,并且h不等于c的左孩子,也不等于c的右孩子,则把c的左孩子压入stack中。具体解释一下这么做的原因,首先h的意义是最近一次弹出并打印的节点,所以如果h等于c的左孩子或者右孩子,说明c的左子树与右子树已经打印完毕,此时不应该再将c的左孩子放入stack中。否则,说明左子树还没处理过,那么此时将c的左孩子压入stack中。

②:如果条件①不成立,并且c的右孩子不为null,h不等于c的右孩子,则把c的右孩子压入stack中。含义是如果h等于c的右孩子,说明c的右子树已经打印完毕,此时不应该再将c的右孩子放入stack中。否则,说明右子树还没处理过,此时将c的右孩子压入stack中。

③:如果条件①和条件②都不成立,说明c的左子树和右子树都已经打印完毕,那么从stack中弹出c并打印,然后令h=c。

3.一直重复步骤2,直到stack为空,过程停止。”

非递归实现二叉树的后序遍历方式2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//方法二:只使用一个栈实现二叉树的非递归后序遍历
//✅
//思路:使用一个栈和两个变量,h代表上次访问并删除的节点,c代表当前节点
func PostorderTraverseNoRecursionII(root *TreeNode) []int {
if root == nil {
return nil
}

var ret []int
stack := []*TreeNode{root}

//初始化的时候h置为root,将c置为nil
h := root
var c *TreeNode

//如果栈不为空
for len(stack) != 0 {
c = stack[len(stack)-1]
//如果当前节点的左子树不为空,并且左右子树都不等于h,说明左子树没有遍历过,将左节点加入栈中
if c.Left != nil && h != c.Left && h != c.Right { //也就是第一次遍历该节点的时候
stack = append(stack, c.Left)
} else if c.Right != nil && c.Right != h { //如果当前节点的右子树不为空,且不等于h,说明没有遍历过,则将右节点加入到栈中,也就是第二次遍历该节点的时候
stack = append(stack, c.Right)
} else { //否则,弹出节点,并加入到结果中,也就是第三次遍历该节点的时候
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
ret = append(ret, node.Val)
//并且将上一次访问并且打印过的节点重置为node
h = node
}
}

return ret
}
【推荐】第三种方式:

后序遍历是按照左->右->根的顺序遍历,我们可以按照根->右->左的顺序遍历,然后将我们的结果反转即可。

非递归实现二叉树的后序遍历方式3:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func PostOrderTraverseNoRecursion(root *TreeNode) []int {
if root == nil {
return nil
}

var ret []int
stack := []*TreeNode{root}

//按照根右左的顺序遍历之后反转我们的结果
for len(stack) != 0 {
cur := stack[len(stack)-1]
stack = stack[:len(stack)-1]
ret = append(ret, cur.Val)
if cur.Left != nil { //加入左
stack = append(stack, cur.Left)
}
if cur.Right != nil { //加入右
stack = append(stack, cur.Right)
}
}

//反转我们的ret
for i := 0; i < len(ret)>>1; i++ {
ret[i], ret[len(ret)-1-i] = ret[len(ret)-1-i], ret[i]
}
fmt.Println(ret)

return ret
}

评论