(Leet Code c++)Invert Binary Tree

226. Invert Binary Tree

 

Given the root of a binary tree, invert the tree, and return its root.

 

Example 1:

Input: root = [4,2,7,1,3,6,9] Output: [4,7,2,9,6,3,1]

Example 2:

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

Example 3:

Input: root = [] Output: []

 

Constraints:

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

주어진 이진 트리를 반대로 뒤집어서 리턴하면 된다.

재귀함수로 구현.

 

매개 변수로 받은 root가 NULL이라면 바로 root를 리턴.

 

root가 NULL이 아니라면,

swap() 함수를 통해 왼쪽과 오른쪽을 바꿔준다.

그리고 다시 invertTree() 함수를 통해 root의 왼쪽부터 방문한 뒤,

root의 오른을 방문하면 끝이다!

/**
 * 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:
    TreeNode* invertTree(TreeNode* root) {
        if(root != NULL){
            swap(root->left, root->right);
            
            invertTree(root->left);
            invertTree(root->right);
            
            return root;
        }
        else{
            return root;
        }
    }
};