[leetcode]226-翻转二叉树

马谦马谦马谦

615
文章

17
评论

2020 年 2 月 26 日 22:46:58数据结构和算法评论241字数 513阅读 1 分 42 秒阅读模式

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/invert-binary-tree

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

翻转一棵二叉树。

示例：

输入：

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

/ \

2 7

/ \ / \

1 3 6 9

输出：

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

/ \

7 2

/ \ / \

9 6 3 1

二、题解

简单题，有两种思路：递归和队列。

2.1 递归

每遍历到一个节点，调整左右子树的值。然后分别递归遍历左右子树。

TreeNode *invertTree(TreeNode *root) {
    TreeNode *p;

    if (root == nullptr) {
        return nullptr;
    }

    // 调整左右子树
    p = root->left;
    root->left = root->right;
    root->right = p;

    // 遍历左右子树
    invertTree(root->left);
    invertTree(root->right);

    return root;
}

TreeNode *invertTree(TreeNode *root) {

TreeNode *p;

if (root == nullptr) {

return nullptr;

}

// 调整左右子树

p = root->left;

root->left = root->right;

root->right = p;

// 遍历左右子树

invertTree(root->left);

invertTree(root->right);

return root;

}

2.2 使用队列

把根节点放到队列中，然后依次访问队列中的节点，把每个节点的左右子树位置对换，然后把左右子节点放到栈中继续遍历。

TreeNode *invertTree(TreeNode *root) {
    queue<TreeNode *> q;
    TreeNode *node, *tmp;

    if (root == nullptr) {
        return nullptr;
    }

    // 根节点入队
    q.push(root);
    while (!q.empty()) {
        // 取队首元素
        node = q.front();
        q.pop();

        // 调换左右子树
        tmp = node->left;
        node->left = node->right;
        node->right = tmp;

        // 左子树入队
        if (node->left) {
            q.push(node->left);
        }
        // 右子树入队
        if (node->right) {
            q.push(node->right);
        }
    }

    return root;
}