[LeetCode] 872. Leaf-Similar Trees

https://leetcode.com/problems/leaf-similar-trees/description/

Leaf-Similar Trees - LeetCode

leetcode - Lear-Similar Trees

문제 유형 : 트리, dfs/bfs

문제 난이도 : Easy

 

문제

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.

 

이진 트리의 잎 노드들을 왼쪽에서 오른쪽순으로 만든 순서의 배열을 leaf-value sequence라고 한다.

예를 들어서, 위 트리에서의 leaf-value sequencesms (6,7,4,9,8)이다.

두 이진 트리의 leaf-value sequence가 같으면 잎사귀가 같다고 할 수 있다.

두 개의 트리의 루트가 주어지는데, 둘이 잎사귀가 같은지 판별하시오.

 

 

풀이

전위 순회를 통해서 왼쪽에서 오른쪽순으로 잎 노드를 나열시킨 배열을 두 개 만들어서, 두 배열이 같은지 비교하면 된다.

 

우선, 현재 노드의 자식 노드가 없는경우, 배열에 현재 노드의 값을 추가한다.

자식 노드가 있다면, 각각 왼쪽 서브트리, 오른쪽 서브트리를 루트로 재귀호출한다.

 

두 배열이 만들어졌다.

우선 길이부터 체크하고, 그 뒤로 순차적으로 한 요소씩 비교해주면 된다.

 

 

코드

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

static const auto __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    void traverse(TreeNode* root, vector<int> &seq) {
        if(!root -> left && !root -> right) {
            seq.push_back(root -> val);
            return;
        }

        if(root -> left) {
            traverse(root -> left, seq);
        }
        if(root -> right) {
            traverse(root -> right, seq);
        }
    }

    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> seq1, seq2;
        traverse(root1, seq1);
        traverse(root2, seq2);

        if(seq1.size() != seq2.size()) return false;
        for(int i = 0; i < seq1.size(); i++) {
            if(seq1[i] != seq2[i]) return false;
        }
        return true;
    }
};