Binary Tree: Level Order Traversal

16th March 2021 at 11:49am
Binary Tree

按层来遍历二叉树。思路非常简单,用 FIFO 队列来解决就好。

下面的代码以这颗树为测试用例:

       1
      / \
     2   3
    / \   \
   4   5   6
  /       / \
 7       8   9
              \
              10
package main

import "fmt"

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

func levelOrderTraversal(root *TreeNode) []int {
    queue := []*TreeNode{root}
    answer := []int{}

    for len(queue) != 0 {
        curr := queue[0]
        answer = append(answer, curr.Val)
        queue = queue[1:]

        if curr.Left != nil {
            queue = append(queue, curr.Left)
        }
        if curr.Right != nil {
            queue = append(queue, curr.Right)
        }
    }
    return answer
}

func main() {
    root := &TreeNode{1,
        &TreeNode{2,
            &TreeNode{4, &TreeNode{7, nil, nil}, nil},
            &TreeNode{5, nil, nil}},
        &TreeNode{3, nil,
            &TreeNode{6,
                &TreeNode{8, nil, nil},
                &TreeNode{9,
                    nil,
                    &TreeNode{10, nil, nil},
                },
            }}}
    fmt.Println(levelOrderTraversal(root))
}