本文共 1886 字，大约阅读时间需要 6 分钟。

Invert a binary tree.

Example:

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

Output:

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

Trivia:

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.

题意：翻转一棵二叉树。

思路1：先序遍历。代码如下：

class Solution {
   public:    TreeNode* invertTree(TreeNode* root) {
           if (!root) return root;        swap(root->left, root->right);        root->left = invertTree(root->left);        root->right = invertTree(root->right);        return root;    }};

效率：

执行用时：4 ms, 在所有 C++ 提交中击败了60.36% 的用户内存消耗：9.3 MB, 在所有 C++ 提交中击败了52.45% 的用户

思路2：中序遍历。代码如下：

class Solution {
   public:     TreeNode* invertTree(TreeNode* root) {
           if (!root) return root;        invertTree(root->left); //递归找到左结点        swap(root->left, root->right);        invertTree(root->left); //此时左右结点已经交换        return root;    }};

效率如下：

执行用时：4 ms, 在所有 C++ 提交中击败了60.36% 的用户内存消耗：9.2 MB, 在所有 C++ 提交中击败了61.82% 的用户

思路3：后序遍历。代码如下：

class Solution {
   public:    TreeNode* invertTree(TreeNode* root) {
           if (!root) return root;        root->left = invertTree(root->left);        root->right = invertTree(root->right);        swap(root->left, root->right);        return root;    }};

效率：

执行用时：4 ms, 在所有 C++ 提交中击败了60.36% 的用户内存消耗：9.3 MB, 在所有 C++ 提交中击败了41.42% 的用户

思路4：层序遍历。代码如下：

class Solution {
   public:    TreeNode* invertTree(TreeNode* root) {
           if (root == nullptr) return root;        queue
   
     q;        q.push(root);         while (!q.empty()) {
               TreeNode *t = q.front(); q.pop();            swap(t->left, t->right);            if (t->left) q.push(t->left);            if (t->right) q.push(t->right);        }        return root;    } };
   

效率：

执行用时：0 ms, 在所有 C++ 提交中击败了100.00% 的用户内存消耗：9.4 MB, 在所有 C++ 提交中击败了15.61% 的用户

转载地址：https://memcpy0.blog.csdn.net/article/details/108245798 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！