leetcode 链接：226. 翻转二叉树

题目

翻转一棵二叉树。

示例：
输入：

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

输出：

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

解答 & 代码

解法一：递归（深度优先遍历）

/**
 * 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 == nullptr)
            return nullptr;

        TreeNode* left = root->left;
        TreeNode* right = root->right;
        root->left = invertTree(right);
        root->right = invertTree(left);
        return root;
    }
};

执行结果：

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 57.08% 的用户
内存消耗：9.5 MB, 在所有 C++ 提交中击败了 29.99% 的用户

解法二：非递归（广度优先遍历）

/**
 * 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 == nullptr)
            return nullptr;

        queue<TreeNode*> nodeQ;
        nodeQ.push(root);
        while(!nodeQ.empty())
        {
            TreeNode* cur = nodeQ.front();
            nodeQ.pop();
            if(cur->left != nullptr)
                nodeQ.push(cur->left);
            if(cur->right != nullptr)
                nodeQ.push(cur->right);
            // 交换左右子树
            TreeNode* left = cur->left;
            cur->left = cur->right;
            cur->right = left;
        }
        return root;
    }
};

执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了 7.51% 的用户
内存消耗：9.7 MB, 在所有 C++ 提交中击败了 5.29% 的用户