LeetCode226. Invert Binary Tree（二叉树 / 模拟）

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日 星期四