(Leet Code c++)Symmetric Tree

101. Symmetric Tree

 

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

 

Example 1:

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

Example 2:

Input: root = [1,2,2,null,3,null,3] Output: false

 

Constraints:

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

루트의 왼쪽 자식에 있는 원소들과 오른쪽 자식에 있는 원소들이 서로 대칭인지 확인하는 문제.

전위 순회를 바탕으로 왼쪽 노드 먼저 방문하는 전위 순회 함수, 오른쪽 노드를 먼저 방문하는 전위 순회 함수를 정의해 방문했다.

 

preorderLeft() 함수는 루트의 왼쪽 자식 노드가 루트가 되고, 현재 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순서로 순회한다.

preorderRight() 함수는 루트의 오른쪽 자식 노드가 루트가 되고, 현재 노드 -> 오른쪽 자식 노드 -> 왼쪽 자식 노드 순서로 순회한다.

 

순회를 통해 value를 각각 a, b 벡터에 저장했다.

두 벡터의 사이즈가 같지 않다면 바로 false를 리턴.

사이즈가 같다면 원소가 서로 같은지 확인하면 된다.

같지 않다면 false를 리턴,

모두 같다면 while문을 탈출해 ture를 리턴하게 된다.

/**
 * 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) {}
 * };
 */
class Solution {
public:
    void preorderLeft(TreeNode * node, vector<int> &v){
        v.push_back(node->val);
        
        if(node->left != NULL){
            preorderLeft(node->left, v);
        }
        else{
            v.push_back(200);
        }
        
        if(node->right != NULL){
            preorderLeft(node->right, v);
        }
        else{
            v.push_back(200);
        }
    }
    
    void preorderRight(TreeNode * node, vector<int> &v){
        v.push_back(node->val);
        
        if(node->right != NULL){
            preorderRight(node->right, v);
        }
        else{
            v.push_back(200);
        }
        
        if(node->left != NULL){
            preorderRight(node->left, v);
        }
        else{
            v.push_back(200);
        }
    } 
    
    bool isSymmetric(TreeNode* root) {
        vector<int> left;
        vector<int> right;
        
        if(root != NULL){
            int aIndex = 0;
            int bIndex = 0;
            
            if(root-> left != NULL){
                preorderLeft(root->left, left);
            }
            
            if(root->right != NULL){
                preorderRight(root->right, right);
            }
            
            if(left.size() != right.size()){
                return false;
            }
            else{
                while(aIndex < left.size() && bIndex < right.size()){
                    if(left[aIndex++] != right[bIndex++]){
                        return false;
                    }
                }
            }
        }
        
        return true;
    }
};