[LeetCode] 1372. Longest ZigZag Path in a Binary Tree(Kotlin)

[LeetCode] 1372. Longest ZigZag Path in a Binary Tree(Kotlin)

• https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/description/

풀이

• 이진 트리 층별 순회하며, 각 노드에서 시작하는 지그재그 경로의 최대 길이 계산하기

import java.util.Deque

class Solution {
    fun longestZigZag(root: TreeNode?): Int{
        if(root == null) return 0

        var longestZigZagPath = 0
        // 이진 트리 층별 순회
        val q = ArrayDeque<TreeNode?>()
        q.addLast(root)
        while(!q.isEmpty()){
            val curNode = q.first()
            q.removeFirst()
            
            if(curNode == null) continue

            longestZigZagPath = max(longestZigZagPath, getZigZag(curNode, true))
            longestZigZagPath = max(longestZigZagPath, getZigZag(curNode, false))
            
            q.addLast(curNode.left)
            q.addLast(curNode.right)
        }
        return longestZigZagPath -1
    }
	
    // 지그재그 이동 경로 길이 반환
    private fun getZigZag(root: TreeNode?, goLeft: Boolean): Int{
        if(root == null) return 0 

        val childNode = if(goLeft) root.left else root.right
        return  1 + getZigZag(childNode, !goLeft)
    }
}

더 나은 풀이

• 메모이제이션을 쓴다거나...더 나은 풀이를 생각해보자!!!!!!