翻转二叉树

翻转一棵二叉树。

递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
#define MAX_SIZE 10000

struct TreeNode* invertTree(struct TreeNode* root){
    if (!root) {
        return NULL;
    }
    
    struct TreeNode *tmp = root->left;
    root->left = root->right;
    root->right = tmp;

    invertTree(root->left);
    invertTree(root->right);
    return root;
}

迭代

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
#define MAX_SIZE 10000

struct TreeNode* invertTree(struct TreeNode* root){
    if (!root) {
        return NULL;
    }
    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * MAX_SIZE);
    int top = -1;
    stack[++top] = root;
    while (top != -1) {
        struct TreeNode* p = stack[top--];

        struct TreeNode* tmp = p->left;
        p->left = p->right;
        p->right = tmp;

        if (p->left) {
            stack[++top] = p->left;
        }
        if (p->right) {
            stack[++top] = p->right;
        }
    }
    return root;
}

BFS(广度优先遍历)

如果对树的遍历比较熟悉的话，我们只要遍历树的所有节点，然后把他们的左右子节点相互交换即可，如果这样写，那么答案就比较多了。这里来看下二叉树的BFS解法，二叉树的BFS就是一层一层的遍历，下面这样:

广度优先遍历.png

#define MAX_SIZE 10000
struct TreeNode* treeBFS(struct TreeNode* root) {
    if (!root) {
        return NULL;
    }
    struct TreeNode** queue = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * MAX_SIZE);
    int head = 0, rear = 0;
    // 相当于把数据加入到队列尾部
    queue[rear++] = root;
    while (head < rear) {
        int size = rear - head;
        for (int i = 0; i < size; i++) {
            struct TreeNode* p = queue[head++];
            // 先插入左节点
            if (p->left) {
                queue[rear++] = p->left;
            }
            // 再插入右节点
            if (p->right) {
                queue[rear++] = p->right;
            }
        }
    }
    return root;
}

我们就参照这种方式来写下，每次遍历节点的时候都要交换子节点，所以代码很容易写，二叉树的BFS代码如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
#define MAX_SIZE 10000
struct TreeNode* invertTree(struct TreeNode* root) {
    if (!root) {
        return NULL;
    }
    struct TreeNode** queue = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * MAX_SIZE);
    int head = 0, rear = 0;
    queue[rear++] = root;
    while (head < rear) {
        int size = rear - head;
        for (int i = 0; i < size; i++) {
            struct TreeNode* p = queue[head++];
            // 交换左右节点
            struct TreeNode* tmp = p->left;
            p->left = p->right;
            p->right = tmp;
            // 插入左节点
            if (p->left) {
                queue[rear++] = p->left;
            }
            // 插入右节点
            if (p->right) {
                queue[rear++] = p->right;
            }
        }
    }
    return root;
}

DFS(深度优先遍历)

上面说了只要能遍历二叉树的所有节点，然后交换子节点，就能完成这道题，二叉树还有一种方式是DFS遍历，他的代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
#define MAX_SIZE 10000
struct TreeNode* treeDFS(struct TreeNode* root) {
    if (!root) {
        return NULL;
    }
    struct TreeNode** queue = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * MAX_SIZE);
    int head = 0, rear = 0;
    // 相当于把数据加入到队列尾部
    queue[rear++] = root;
    while (head < rear) {
        int size = rear - head;
        for (int i = 0; i < size; i++) {
            struct TreeNode* p = queue[head++];
            // 右节点先入队
            if (p->right) {
                queue[rear++] = p->right;
            }
            // 左节点再入队
            if (p->left) {
                queue[rear++] = p->left;
            }
        }
    }
    return root;
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
#define MAX_SIZE 10000
struct TreeNode* invertTree(struct TreeNode* root) {
    if (!root) {
        return NULL;
    }
    struct TreeNode** queue = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * MAX_SIZE);
    int head = 0, rear = 0;
    queue[rear++] = root;
    while (head < rear) {
        int size = rear - head;
        for (int i = 0; i < size; i++) {
            struct TreeNode* p = queue[head++];
            // 交换左右节点
            struct TreeNode* tmp = p->left;
            p->left = p->right;
            p->right = tmp;
            // 右节点先入队
            if (p->right) {
                queue[rear++] = p->right;
            }
            // 左节点再入队
            if (p->left) {
                queue[rear++] = p->left;
            }
        }
    }
    return root;
}