侧边栏壁纸
博主头像
Hope博主等级

努力赚钱的工科研究生

  • 累计撰写 362 篇文章
  • 累计创建 129 个标签
  • 累计收到 5 条评论
标签搜索

LeetCode 226. 翻转二叉树

Hope
2022-03-17 / 0 评论 / 0 点赞 / 286 阅读 / 682 字
温馨提示:
本文最后更新于 2022-03-17,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

LeetCode 226. 翻转二叉树

思路:

刚开始的想法是二叉树层序遍历记录每一层,用一个二维数组存下来,反转每一层之后然后再遍历一次,依次赋值,O(n)。

然后发现递归一下好像也可以,算法O(logn)

代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return root;
        auto p = root;
        Reverse(root);
        return p;
    }

    void Reverse(TreeNode* root){
        if(!root) return;
        if(root->left) Reverse(root->left);
        if(root->right)  Reverse(root->right);
        auto tmp = root->left;
        root->left = root->right;
        root->right = tmp;
    }
};
0

评论区