首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【LeetCode】每日一题(8.2)二叉树展开为链表

【LeetCode】每日一题(8.2)二叉树展开为链表

作者头像
看、未来
发布2020-08-25 12:01:46
2740
发布2020-08-25 12:01:46
举报

二叉树展开为链表

给定一个二叉树,原地将它展开为一个单链表。

例如,给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6

将其展开为:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

具体做法是,对于当前节点,如果其左子节点不为空,则在其左子树中找到最右边的节点,作为前驱节点,将当前节点的右子节点赋给前驱节点的右子节点(其实就是找左子节点的最大子节点),然后将当前节点的左子节点赋给当前节点的右子节点,并将当前节点的左子节点设为空。对当前节点处理结束后,继续处理链表中的下一个节点,直到所有节点都处理结束。

刚开始我想用前序遍历,但是弄来弄去把我自己都弄晕了,到底什么叫“原地”?题目里说要原地。 后来想了想,这个题其实有规律的。

不过这个解法的时间复杂度我不太会算。。。

代码

class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode *curr = root;
        while (curr != nullptr) {
            if (curr->left != nullptr) {
                auto next = curr->left;
                auto predecessor = next;
                while (predecessor->right != nullptr) {
                    predecessor = predecessor->right;
                }
                predecessor->right = curr->right;
                curr->left = nullptr;
                curr->right = next;
            }
            curr = curr->right;
        }
    }
};

复杂度

时间复杂度:O(n),其中 n 是二叉树的节点数。展开为单链表的过程中,需要对每个节点访问一次,在寻找前驱节点的过程中,每个节点最多被额外访问一次。(官方解法算的)

空间复杂度:O(1)。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-08-02 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 二叉树展开为链表
  • 思路
  • 代码
  • 复杂度
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档