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

兄弟们，写到了1点了快

1、层序遍历

题目：
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

思路：

• 左侧也要加进去的，万有右侧没有看左侧
• 取每层最后一个元素，原来是这样，呜呜，没想到啊，
• 用的list.New,这也可以当队列用，wc，太好用了吧
• 记录 queue.Len() 是为了弹出当前层的节点

func rightSideView(root *TreeNode) []int {
    //代码一刷，层序遍历
    if root == nil {
        return nil
    }
    res := []int{}
    queue := list.New()
    queue.PushBack(root)

    for queue.Len() != 0 {
        length := queue.Len()
        for i:=0; i<length; i++ {
            node := queue.Remove(queue.Front()).(*TreeNode)
            if node.Left != nil {
                queue.PushBack(node.Left) 
            }
            if node.Right != nil {
                queue.PushBack(node.Right) 
            } 

            if i==length-1 {
                res = append(res, node.Val)
            }
        }
    }
    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

2、226. 翻转二叉树

题目：
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

思路：

• 有递归，迭代，层序法
• 递归，节点交换即可

func invertTree(root *TreeNode) *TreeNode {
    // 代码一刷，翻转，递归,中序
    if root == nil {
        return root
    }
    invertTree(root.Left)
    root.Left, root.Right = root.Right, root.Left
    invertTree(root.Left)
    return root
}
1
2
3
4
5
6
7
8
9
10

3、101. 对称二叉树

题目：
给你一个二叉树的根节点 root ， 检查它是否轴对称。

思路：

• 这个判断的条件，很有顺序的哦
• 比较内外层元素是否相同，后序，下钻

func isSymmetric(root *TreeNode) bool {
    // 代码一刷，后序，递归,有点像反转二叉树哈
    return compare(root.Left, root.Right)
}
func compare(Left, Right *TreeNode) bool {
    if Left == nil && Right == nil {
        return true
    }
    if Left == nil || Right == nil {
        return false
    }
    if Left.Val != Right.Val {
        return false
    }
    return compare(Left.Right, Right.Left) && compare(Left.Left, Right.Right) // 内外层比较，结果返回上一层，后序下钻
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16