给定一棵二叉树的根节点 root，请左右翻转这棵二叉树，并返回其根节点。

示例 1：

**输入：**root = [5,7,9,8,3,2,4]
输出：[5,9,7,4,2,3,8]

提示：

树中节点数目范围在 [0, 100] 内

-100 <= Node.val <= 100

针对子树，根节点的左指针指向翻转后的右子树，右指针指向翻转后的左子树

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    TreeNode *flipTree(TreeNode *root) {
        if (root == nullptr)
            return nullptr;
        TreeNode *mid = root->left;
        root->left = flipTree(root->right);
        root->right = flipTree(mid);
        return root;
    }
};

另一种方法针对结点，根节点的左右指针直接交换指向的结点，接着分别对结点做相应的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    TreeNode *flipTree(TreeNode *root) {
        if (root == nullptr)
            return nullptr;
        TreeNode *mid = root->left;
        root->left = root->right;
        root->right = mid;
        flipTree(root->left);
        flipTree(root->right);
        return root;
    }
};

这种方法可以用栈来模仿递归过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    TreeNode *flipTree(TreeNode *root) {
        if (root == nullptr)
            return nullptr;
        stack<TreeNode *> f;
        f.push(root);
        while (!f.empty()) {
            TreeNode *cur = f.top();
            f.pop();
            if (cur->left != nullptr)
                f.push(cur->left);
            if (cur->right != nullptr)
                f.push(cur->right);
            TreeNode *mid = cur->left;
            cur->left = cur->right;
            cur->right = mid;
        }
        return root;
    }
};