Leetcode - 101. Symmetric Tree

숲사람·2022년 6월 26일
0

멘타트 훈련

목록 보기
73/237

문제

트리가 root를 기준으로 좌우 대칭인지 확인하기.

Input: root = [1,2,2,3,4,4,3]
Output: true


https://leetcode.com/problems/symmetric-tree/

해결

트리의 root->left를 invert_tree 해버리고, 그 후에 root->right와 동일한지 dfs해서 비교하여 해결

class Solution {
private:
    TreeNode *invert_tree(TreeNode *root) {
        if (root == NULL)
            return NULL;
        TreeNode *tmp = root->left;
        root->left = invert_tree(root->right);
        root->right = invert_tree(tmp);
        return root;
    }
    bool dfs(TreeNode *n1, TreeNode *n2) {
        if (n1 == NULL && n2 == NULL)
            return true;
        if ((!n1 && n2) || (n1 && !n2))
            return false;
        if (n1->val != n2->val)
            return false;
        if (!dfs(n1->left, n2->left))
            return false;
        if (!dfs(n1->right, n2->right))
            return false;
        return true; 
    }
public:
    bool isSymmetric(TreeNode* root) {
        invert_tree(root->left);   
        return dfs(root->left, root->right);
    }
};
profile
기록 & 정리 아카이브 용도 (보다 완성된 글은 http://soopsaram.com/documentudy)

0개의 댓글