刷题笔记day15-二叉树层序遍历

层序遍历

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

import (
    "container/list"
)

func levelOrder(root *TreeNode) [][]int {
    // 思路1：此处肯定要使用队列
    result := [][]int{}
    if root == nil {
        return result
    }
    stack := list.New()
    stack.PushBack(root)

    for stack.Len() > 0 {
        
        stackLength := stack.Len()

        // 遍历每一层的所有节点
        newLis := []int{}
        for i := 0; i < stackLength; i++ {
            top := stack.Remove(stack.Front())
            node := top.(*TreeNode)
            newLis = append(newLis, node.Val)
            if node.Left != nil {
                stack.PushBack(node.Left)
            }
            if node.Right != nil {
                stack.PushBack(node.Right)
            }
        }
        result = append(result, newLis)
    }
    return result
}

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

107. 二叉树的层序遍历 II

这个题的意思是从底到上进行层次遍历。我就直接将上一题的从上到下的遍历结果，做一次翻转既可。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func levelOrderBottom(root *TreeNode) [][]int {
    // 思路：相当于是之前从顶往下的结果，反转一下
    // 这次使用自定义的队列吧，就不使用 container/list 了
    var (
        result [][]int
    )
    if root == nil {
        return result
    }
    var que []*TreeNode
    que = append(que, root)

    for len(que) > 0 {
        length := len(que)
        partResult := []int{}
        for i := 0; i < length; i++ {
            front := que[0]
            que = que[1:]
            partResult = append(partResult, front.Val)
            if front.Left != nil {
                que = append(que, front.Left)
            }
            if front.Right != nil {
                que = append(que, front.Right)
            }
        }
        result = append(result, partResult)
    }
    // 反转结果
    var newResult [][]int
    for i := len(result) - 1; i >= 0; i-- {
        newResult = append(newResult, result[i])
    }
    return newResult
}

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

199. 二叉树的右视图

目的：
思路：还是层次遍历，判断每一层 index 是否是最后一个。如果是，则将结果追加到result中。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
import "container/list"

func rightSideView(root *TreeNode) []int {
    // 我的思路是，层次遍历，每次访问一层的最右边的点。
    var result []int
    if root == nil {
        return result
    }
    que := list.New()
    que.PushBack(root)

    for que.Len() > 0 {
        length := que.Len()
        for i := 0; i < length; i++ {
            front := que.Remove(que.Front())
            node := front.(*TreeNode)

            // 每层最后一个放入result中。
            if i == length - 1 {
                result = append(result, node.Val)
            }
            if node.Left != nil {
                que.PushBack(node.Left)
            }
            if node.Right != nil {
                que.PushBack(node.Right)
            }
        }
    }
    return result
}
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

637. 二叉树的层平均值

还是层次遍历的思路，计算每一层的平均值。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
import "container/list"

func averageOfLevels(root *TreeNode) []float64 {
    // 思路：还是层次遍历，计算每一层的平均值。
    var result []float64
    if root == nil {
        return result
    }
    que := list.New()
    que.PushBack(root)

    for que.Len() > 0 {
        sum := 0
        length := que.Len()
        for i := 0; i < length; i++ {
            front := que.Remove(que.Front())
            node := front.(*TreeNode)
            sum += node.Val
            
            if node.Left != nil {
                que.PushBack(node.Left)
            }
            if node.Right != nil {
                que.PushBack(node.Right)
            }
        }
        result = append(result, float64(sum) / float64(length))
    }
    return result
}
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

429. N 叉树的层序遍历

换汤不换药

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */
 import "container/list"

func levelOrder(root *Node) [][]int {
    // 思路大差不差，依旧是层次遍历
    var result [][]int
    if root == nil {
        return result
    }
    que := list.New()
    que.PushBack(root)
    for que.Len() > 0 {
        length := que.Len()
        var partResult []int
        for i := 0; i < length; i++ {
            front := que.Remove(que.Front())
            node := front.(*Node)
            partResult = append(partResult, node.Val)
            for _, item := range node.Children {
                que.PushBack(item)
            }
        }
        result = append(result, partResult)
    }
    return result
}
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

515.在每个树⾏中找最⼤值

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func largestValues(root *TreeNode) []int {
    var result []int
    if root == nil {
        return result
    }
    que := list.New()
    que.PushBack(root)

    for que.Len() > 0 {
        length := que.Len()
        maxValue := que.Front().Value.(*TreeNode).Val
        for i := 0; i < length; i++ {
            front := que.Remove(que.Front())
            node := front.(*TreeNode)

            // 每层最后一个放入result中。
            if node.Val > maxValue {
                maxValue = node.Val
            }
            if node.Left != nil {
                que.PushBack(node.Left)
            }
            if node.Right != nil {
                que.PushBack(node.Right)
            }
        }
        result = append(result, maxValue)
    }
    return result
}
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

226.翻转二叉树

不可以使用 中序遍历，因为左边的调整完后，返回到根节点后，左边的换到右边，这是又开始调整“左边的”了，相当与右边的没动。
可是使用前序遍历、后序遍历。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func invertTree(root *TreeNode) *TreeNode {
    // 思路：利用递归遍历，进行调整
    // 不可以使用 中序遍历，因为左边的调整完后，返回到根节点后，左边的换到右边，这是又开始调整“左边的”了，相当与右边的没动。
    // 三部曲：参数和返回值、单层逻辑、终止条件
    // 前序遍历:根左右
    if root == nil {
        return nil
    }
    root.Left, root.Right = root.Right, root.Left
    invertTree(root.Left)
    invertTree(root.Right)
    return root
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

101. 对称二叉树

使用递归的方法，比较左子树的左边和右子树的右边，以及右子树的右节点和右子树的左节点进行比较。
遍历方式：前序遍历

func isSymmetric(root *TreeNode) bool {
    // 思路：直接使用递归的方法，进行前序遍历，查看左右子树的值是否一样
    if root == nil {
        return true
    }
    return traversal(root.Left, root.Right)
}


func traversal(left *TreeNode, right *TreeNode) bool {
    if left == nil && right == nil {
        return true
    } else if left == nil || right == nil {
        return false
    }

    // 判断是否相等
    if left.Val != right.Val {
        return false
    }

    part1 := traversal(left.Left, right.Right)
    if !part1 {
        return false
    }
    part2 := traversal(left.Right, right.Left)
    if !part2 {
        return false
    }
    return true
}
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