[Leetcode]- Longest ZigZag Path in a Binary Tree (2023/04/19)

You are given the root of a binary tree.

A ZigZag path for a binary tree is defined as follow:

• Choose any node in the binary tree and a direction (right or left).
• If the current direction is right, move to the right child of the current node; otherwise, move to the left child.
• Change the direction from right to left or from left to right.
• Repeat the second and third steps until you can't move in the tree.

Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0).

Return the longest ZigZag path contained in that tree.

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

 

 

Constraints: 

• The number of nodes in the tree is in the range [1, 5 * 104].
• 1 <= Node.val <= 100

 

Hint 1

트리의 루트가 주어지므로, greedy방식은 사용할 수 없다. brute force로 접근한다.

 

Hint 2

zig-zag가 아닌 루트로 빠질 경우, 이전 경로가 아닌 새로운 경로로 생각한다.

 

Hint 3

현재 노드에서 할 수 있는 작업은 새로운 경로를 생성하거나, 이전 경로를 잇는 경우 두가지로 나뉜다.

 

Approach

 

1. DFS를 통해 완전 탐색을 시행한다.

 

/**
* @params {treeNode | null} root
* @params {number} dir - -1 혹은 1 , 
* @params {number} cnt
*/
function dfs(root, dir, cnt){

        if(!root){
        	// 현재 노드는 null 이므로 경로에서 제외한다.
            return cnt - 1;
        }

        let left,right;
		// 좌측으로 욺직여야 이전 zigzag를 잇는 경우
        if(dir < 0){
            // 우측으로 욺직이면 이전 zigzag를 잇지 못하므로, 초기화.
            right = dfs(root.right, dir , 1 );
            // 좌측으로 이동하였기에, 이전 zigzag를 이었음. cnt + 1통해 이전 zigzag를 잇는다.
            left = dfs(root.left, -dir, cnt + 1);
 
        }else{ // 우측으로 욺직여야 이전 zigzag를 잇는 경우
            right = dfs(root.right, -dir , cnt + 1);
            left = dfs(root.left, dir, 1);
        }

        const pathLength = Math.max(left,right);
        return pathLength        
  }

 

2. root 노드의 대해서, 좌측으로 욺직인 경우, 우측으로 욺직인 경우 두가지 경우의 수가 발생 하므로, 각 경우에 대해 dfs를 두번시행한다.

var longestZigZag = function(root) {

        function dfs(root, dir, cnt){

            if(!root){
                return cnt - 1;
            }

            let left,right;

            if(dir < 0){
                right = dfs(root.right, dir , 1 );
                left = dfs(root.left, -dir, cnt + 1);

            }else{ 
                right = dfs(root.right, -dir , cnt + 1);
                left = dfs(root.left, dir, 1);
            }

            const pathLength = Math.max(left,right);
            return pathLength        
      }
    const left = dfs(root , -1 , 0 , 0);
    const right = dfs(root, 1 , 0, 0);
    return Math.max(left,right)
};

 

 

 

Improvement

해당 문제의 Related topic에 Dynamic Promgramming이 있어서, DP 방식을 적용해보았다.( 다만, 오히려 시간면에서 하위 6%로 떨어졌다.. 필자의 경우 cache Key로써, 전역 심볼을 사용했는데, 아마 글로벌 레지스트리에 접근하면서 시간적 손실을 본듯하다.)

DFS + Memoization

 

var longestZigZag = function(root) {

    const cache = {};

    function dfs(root,dir, cnt , identifier){

        const key = Symbol.for([identifier , dir])
        if(!root){
            return cnt - 1;
        }
        if(cache.hasOwnProperty(key)){
            return cache[key]
        }

        let left,right;
        // previous left
        if(dir < 0){
            right = dfs(root.right, dir , 1 , 2*identifier + 2);
            left = dfs(root.left, -dir, cnt + 1, 2*identifier + 1);
 
        }else{ //previous right
            right = dfs(root.right, -dir , cnt + 1, 2*identifier + 2);
            left = dfs(root.left, dir, 1 , 2*identifier + 1);
        }

        const pathLength = Math.max(left,right);
        cache[key] = pathLength
        return pathLength

        
    }


    const left = dfs(root , -1 , 0 , 0);
    const right = dfs(root, 1 , 0, 0);
    return Math.max(left,right)
};