제목

함수는 지그재그 순서에 따라 두 갈래 트리를 인쇄합니다. 즉, 첫 번째 줄은 왼쪽에서 오른쪽으로, 두 번째 줄은 오른쪽에서 왼쪽으로, 세 번째 줄은 왼쪽에서 오른쪽으로 인쇄합니다. 다른 줄은 이와 같습니다.
예를 들어 두 갈래 나무를 주면[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

다음 단계를 반복한 결과를 반환합니다.

[
  [3],
  [20,9],
  [15,7]
]

팁:
노드 총 수<= 1000
출처: 리코드(LeetCode) 링크:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof

문제 풀이 사고방식

본 문제는 면접문제 32-I-위에서 아래로 두 갈래 나무를 인쇄하는 변화입니다

짝수 인쇄 순서가 반대인 것을 알 수 있는 제목이 있다

따라서 이전 문제의 코드를 토대로 층수가 기이하거나 짝인지 판단하여 노드의 수치가 왼쪽에서 오른쪽으로 인쇄되는지 오른쪽에서 왼쪽으로 인쇄되는지 확인하면 된다

해법 1: 시뮬레이션 대기열

– 실행 시간: 0ms – 메모리 소비량: 3.3MB

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

func levelOrder(root *TreeNode) [][]int {
    if root==nil{
        return nil
    }
    var ret [][]int
    queue := []*TreeNode{root}
    // 0 , 0 
    level:=0
    for len(queue)!=0{
        temp := []*TreeNode{}
        ret = append(ret,make([]int,0))
        for _,v := range queue{
            if level & 1 ==0{
                // ， 
                ret[level]=append(ret[level],v.Val)
            }else{
                // ， 
                s := []int{v.Val}
                ret[level]=append(s,ret[level]...)
            }
            // 
            if v.Left!=nil{
                temp = append(temp,v.Left)
            }
            if v.Right!=nil{
                temp = append(temp,v.Right)
            }
        }
        // 
        queue = temp
        level++
    }
    return ret
}

해법2: 귀속

– 실행 시간: 0ms – 메모리 소비량: 3.3MB

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

func levelOrder(root *TreeNode) [][]int {
    ret=nil
    // 0 , 0 
    build(root,0)
    return ret
}

func build(root *TreeNode,level int){
    if root==nil{
        return
    }

    if level > len(ret)-1{
        ret=append(ret,make([]int,0))
    }

    if level & 1 == 0 {
        // ， 
        ret[level]=append(ret[level],root.Val)
    }else{
        // ， 
        s:=[]int{root.Val}
        ret[level]=append(s,ret[level]...)
    }

    // ， 
    level++
    build(root.Left,level)
    build(root.Right,level)
}

LeetCode 이 문제에서 저도 문제풀이를 제출했습니다. 보시기 바랍니다.닉네임: 사쿠라.