[LeetCode] 226. Invert Binary Tree c++

• 문제

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

출처 : https://leetcode.com/problems/invert-binary-tree/

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

 

 부모 노드를 기준으로 자식 노드의 좌우 대칭을 바꾸는 문제입니다.

 

• 문제 해결

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return root;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

swap()함수는  algorithm에 내장된  STL함수입니다.

swap() 함수는 두 개의 참조가 가르키는 위치의 값을 서로 교환합니다.

 

반복문 사용한 풀이

TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> s;
        s.push(root);
        
        while (!s.empty()) {
            TreeNode* curr = s.top();
            s.pop();
            if (!curr) continue;
            s.push(curr->left);
            s.push(curr->right);
            swap(curr->left, curr->right);
        }
        return root;
}

swap() 함수는 두 개의 참조가 가르키는 위치의 값을 서로 교환합으로 마지막에 교환해도 해당 주소의 값은 바뀌어 있습니다.