[Binary Tree-DFS][Medium] 1372. Longest ZigZag Path in a Binary Tree

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

Longest ZigZag Path in a Binary Tree - LeetCode

 

Q. 주어진 tree에서 zig zag 노드를 찾는다고 할때, 해당 경로의 최대 수를 찾아라. 

노드의 수가 아닌, 경로수를 찾는 것에 유의.

 

Solution. 

 우선 직관적으로 생각해 보면, 특정 노드에서 zig zag 하위 노드를 dfs 하면서 해당 수를 카운팅 한다. 그리고 하위 노드로 이동하고 경로 카운팅을 반복한다. 

TC가 O(NxN)으로 좋지 않다. 

 

한번 탐색으로 필요한 정보를 다 얻어 낼 수 있을지, 문제를 다시 관찰해 보자. 

위 그림에서 알수 있듯이, zig zag가 연결되지 않는 지점에서 카운팅을 초기화 한 후, 하위로 탐색을 지속하면 알고리즘이 의도대로 유지 됨을 알 수 있다. 

의도 대로 로직을 짜 본다. 

 

int longestZigZag_dfs(TreeNode* node, int count, bool isLeft)
{
    if (node == NULL)	return count;

    int left = 0, right = 0;
    if (isLeft)
    {
        right = longestZigZag_dfs(node->right, count + 1, false);
        // 지그재그가 불가한 노드는 카운팅을 초기화 하고 탐색 지속.
        left = longestZigZag_dfs(node->left, 0, true);
    }
    else
    {
    	// 지그재그가 불가한 노드는 카운팅을 초기화 하고 탐색 지속.
        right = longestZigZag_dfs(node->right, 0, false);
        left = longestZigZag_dfs(node->left, count + 1, true);
    }
    return max(left, right);
}
int longestZigZag(TreeNode* root)
{
    if (root == NULL)	return 0;

    int retLeft = longestZigZag_dfs(root->left, 0, true);
    int retRight = longestZigZag_dfs(root->right, 0, false);
    return max(retLeft, retRight);
}

 

 

다행히 O(N)의, 의도대로 결과가 나온다.