MENU

LeetCode226. Invert Binary Tree(二叉树 / 模拟)

2019 年 03 月 07 日 • 阅读: 944 • LeetCode阅读设置

LeetCode226. Invert Binary Tree(二叉树 / 模拟)

  • Easy
  • Accepted:301,365
  • Submissions:527,985

Invert a binary tree.

Example:

Input:

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

Output:

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

Trivia:
This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f* off.

链接

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

题意

反转一颗二叉树。一道有趣的题目: )

题解

使用递归操作,先反转左子树,然后反转右子树,最后将左右儿子结点交换位置。(dfs)

当然也可以使用队列,如果当前结点不位空,那就交换左右儿子结点。(bfs)

代码

  • Runtime: 4 ms, faster than 100.00% of C++ online submissions for Invert Binary Tree.
  • Memory Usage: 9.2 MB, less than 40.49% of C++ online submissions for Invert Binary Tree.
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL)
            return NULL;
        invertTree(root->left);
        invertTree(root->right);
        swap(root->left, root->right);
        return root;
    }
};
  • Runtime: 4 ms, faster than 100.00% of C++ online submissions for Invert Binary Tree.
  • Memory Usage: 9.2 MB, less than 30.37% of C++ online submissions for Invert Binary Tree.
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL)
            return NULL;
        queue <TreeNode*> q;
        q.push(root);
        while (!q.empty())
        {
            int n = q.size();
            for (int i = 0 ; i < n; ++i)
            {
                TreeNode*p = q.front();
                q.pop();
                if (p)
                    swap(p->left, p->right);
                if (p->left != NULL)
                    q.push(p->left);
                if (p->right != NULL)
                    q.push(p->right);
            }
        }
        return root;
    }
};

The end.
2019年3月7日 星期四