【代码随想录】算法训练计划14

1、递归——94. 中序遍历

题目：
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
输入：root = [1,null,2,3]
输出：[1,3,2]

思路：

• 看题意，要不要返回值
• 递归，前中后序递归，都一样，放的位置稍微变一下

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    res := []int{}
    var traversal func(node *TreeNode) 
    traversal = func(node *TreeNode) {
        if node == nil {
            return
        }
        traversal(node.Left)
        res = append(res, node.Val)
        traversal(node.Right)
    }
    traversal(root)
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2、迭代（栈）——144. 前序遍历

题目：
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

思路：

• 用栈模拟，实现迭代
• 开始要判断 root==nil ，否则会出现空指针
• 前后迭代，区别就是反转顺序即可
• go有内置的栈,学习一下如何使用
• 中序迭代的栈模拟过程就不一样了，要再想一遍，画个流程图

 // 代码一刷，前序遍历——迭代法
func preorderTraversal(root *TreeNode) []int {
    res := []int{}

    if root == nil {
        return res
    }

    stack := list.New()
    stack.PushBack(root)

    for stack.Len() > 0 {
        node := stack.Remove(stack.Back()).(*TreeNode)
        res = append(res, node.Val)
        if node.Right != nil {
            stack.PushBack(node.Right)
        }
        if node.Left != nil {
            stack.PushBack(node.Left)
        }
    }
    return res
}

// 迭代——代码一刷，后序遍历
 // go语言没有反转，自己实现一下下
func postorderTraversal(root *TreeNode) []int {
    res := []int{}
    if root == nil {
        return res
    }
    stack := list.New()
    stack.PushBack(root)
    for stack.Len() > 0 {
        node := stack.Remove(stack.Back()).(*TreeNode)
        res = append(res, node.Val)
        if node.Left != nil {
            stack.PushBack(node.Left)
        }
        if node.Right != nil {
            stack.PushBack(node.Right)
        }
    }
    return Reverse(res)
}
func Reverse(res []int) []int {
    n := len(res)
    for i:=0; i<n/2; i++ {
        res[i], res[n-i-1] = res[n-i-1], res[i]
    }
    return res
}

// 迭代，栈模拟，代码一刷
 // 注意想明白，栈的模拟过程，不行就画个流程图
func inorderTraversal(root *TreeNode) []int {
    res := []int{}
    if root == nil {
        return res
    }
    stack := list.New()
    cur := root
    for cur != nil || stack.Len() > 0 {
        if cur != nil {
            stack.PushBack(cur)
            cur = cur.Left
        } else {
            cur = stack.Remove(stack.Back()).(*TreeNode)
            res = append(res, cur.Val)
            cur = cur.Right
        }
    }
    return res
}


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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

3、统一迭代法

题目：
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

思路：

• 前序遍历——统一迭代法，很强
• 不要忘记 continue
• 记得 node 知道 .(*TreeNode)干嘛的
• 知道 e有.Value

func preorderTraversal(root *TreeNode) []int {
    res := []int{}
    if root == nil{
        return res
    }
    stack := list.New()
    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
}
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

4、

题目：