Leetcode - 101. Symmetric Tree

문제

트리가 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);
    }
};