来源:力扣(LeetCode)

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

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

一、题目描述

翻转一棵二叉树。

示例:

输入:

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

输出:

     4
   /   \
  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;
}

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;
}

三、备注

这个问题是受到Max Howell 原问题启发的 :

谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板上写出翻转二叉树这道题,这太糟糕了。

其中的一个评论给也很有意思:

如果我是你,我会把白板从下到上翻转。然后告诉他:那,这就是我翻转的二叉树。

最后修改:2020 年 02 月 26 日
喜欢就给我点赞吧