https://leetcode.cn/problems/invert-binary-tree/

题面

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

示例 1：

img

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

示例 2：

img

1
2
输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

1
2
输入：root = []
输出：[]

提示：

  • 树中节点数目范围在 [0, 100] 内
  • -100 <= Node.val <= 100

代码

递归写法

1
2
3
4
5
6
7
TreeNode* invertTree(TreeNode* root) {
    if (root == NULL) return root;
    swap(root->left, root->right); // 中
    invertTree(root->left);        // 左
    invertTree(root->right);       // 右
    return root;
}

迭代写法（前序）

1
2
3
4
5
6
7
8
9
10
11
12
13
TreeNode* invertTree(TreeNode* root) {
    if (root == NULL) return root;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top(); // 中
        st.pop();
        swap(node->left, node->right);
        if (node->right) st.push(node->right); // 右
        if (node->left) st.push(node->left); // 左
    }
    return root;
}

广搜写法（层序遍历）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
TreeNode* invertTree(TreeNode* root) {
    queue<TreeNode*> que;
    if (root != NULL) que.push(root);
    while (!que.empty()) {
        int size = que.size();
        for (int i = 0; i < size; i++) {
            TreeNode* node = que.front();
            que.pop();
            swap(node->left, node->right); // 节点处理
            if (node->left) que.push(node->left);
            if (node->right) que.push(node->right);
        }
    }
    return root;
}