翻转二叉树

题目描述

翻转一棵二叉树。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入：

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

输出：

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

来源：LeetCode

解法一

从根节点的左右子树开始，互换两个节点的指针，完成根节点的翻转，再递归地翻转左右子树节点的左右节点。递归出口是到达树的底部。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return nullptr;
        TreeNode * temp = root->left;
        root->left = root->right;
        root->right = temp;
        invertTree(root->right);
        invertTree(root->left);
        return root;
    }
};

解法二

二叉树BFS，对遍历到的每一个节点，都对其左右节点进行翻转。
注意：此时push到队列的元素都非空，因为只有非空才会有对子节点翻转的必要。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return nullptr;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            TreeNode * node = q.front();
            q.pop();
            TreeNode * temp = node->left;
            node->left = node->right;
            node->right = temp;
            if(node->left) q.push(node->left);
            if(node->right) q.push(node->right);
        }
        return root;
    }
};