面试题 27. 二叉树的镜像

题目描述

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

示例

例如输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

镜像输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

题解

    vector<int> mirror_tree(TreeNode* root) {
        cout << "before mirror\n";
        print_vector(floorTravel(root));

        if (root == nullptr) return {};
        substutite(root);
        mirror_tree(root->left);
        mirror_tree(root->right);

        cout << "after mirror\n";
        vector<int> res = floorTravel(root);
        return res;
    }

    vector<int> floorTravel(TreeNode* root) {
        if (root == nullptr) return {};
        vector<int> res;
        std::queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* cur_pop = q.front();
            if (cur_pop->left) q.push(cur_pop->left);
            if (cur_pop->right) q.push(cur_pop->right);
            res.push_back(cur_pop->val);
            q.pop();
        }
        return res;
    }
    void substutite(TreeNode* root) {
        TreeNode* l = root->left;
        root->left = root->right;
        root->right = l;
    }