[LeetCode] Leaf-Similar Trees

https://leetcode.com/problems/leaf-similar-trees/description/?envType=study-plan-v2&envId=leetcode-75

 

Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).
Two binary trees are considered leaf-similar if their leaf value sequence is the same.
Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

 
Example 1:

 

 

Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Output: true

 

Example 2:

 

 

Input: root1 = [1,2,3], root2 = [1,3,2]
Output: false
 

Constraints:
The number of nodes in each tree will be in the range [1, 200].
Both of the given trees will have values in the range [0, 200].

---

 

두 개의 리프 트리를 차례대로 왼쪽부터 오른쪽으로 탐색해서,

가장 하위에 있는 리프 노드들을 나열했을 때 순서와 값이 동일하면 두 트리는 비슷하다고 간주한다.

주어진 두 개의 트리가 비슷한 지 리턴하는 문제.

 

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {boolean}
 */

var leafSimilar = function(root1, root2) {
    let bottomLeaves1 = [];
    let bottomLeaves2 = [];

    const search = (root, arr) => {
        root.left && search(root.left, arr);
        root.right && search(root.right, arr);
        if(!root.left && !root.right){
            arr.push(root.val);
        }
    }
    search(root1, bottomLeaves1);
    search(root2, bottomLeaves2);
    return bottomLeaves1.join("|") == bottomLeaves2.join("|");
};

 

어제 리프트리 문제를 풀어서 그런지? 뭔지? 생각보다 금방 풀었다!

우선 왼쪽부터 먼저 탐색을 쭉 한 다음, 왼쪽도 오른쪽도 없는 경우 마지막 리프라고 간주하고, leaves 배열에 추가한다.

그렇게 두 번 진행한 다음 구분자로 배열을 join해서 같은지 봐 주면 끝~

자바스크립트는 기본적으로 동기적으로 작동하기 때문에...

left가 있는지 먼저 확인하고 함수를 실행시키는 것만으로도 왼쪽부터 오른쪽으로 탐색시킬 수 있다! 동기 짱~

 

근데 내가 작성한 코드는..

외부에서 배열을 만들어서 넘겨 주어야 하기때문에 재사용성도 떨어지고, 엄밀히 따지면 순수 함수도 아니다.

그런 부분을 좀 더 개선한 건 이렇게!

var leafSimilar = function(root1, root2) {
    const search = (root)=>{
        let arr = [];
        const dfs = (root) => {
            root.left && dfs(root.left, arr);
            root.right && dfs(root.right, arr);
            if(!root.left && !root.right){
                arr.push(root.val);
            }
        }
        dfs(root);
        return arr;
    }
    const bottomLeaves1 = search(root1);
    const bottomLeaves2 = search(root2);
    return bottomLeaves1.join("|") == bottomLeaves2.join("|");
};

 

아무튼 오늘은 뿌듯하고 덜 고통스럽게 끝~

대부분이 0ms이긴 하지만...

그래도 첫 트라이에 이런 결과가 나오는 경우 흔치 않기 때문에 기념으로 남겨본다.