二叉树转链表

给定一个二叉树,将该二叉树 就地(in-place)转换为单链表。单链表中节点顺序 为二叉树前序遍历顺序。(不额外开辟存储空间) LeetCode 114. Flatten Binary Tree to Linked List

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) :
        val(x), left(NULL), right(NULL){} 
};//但链表仍使用该数据结构,即left =NULL,right = next;
class Solution{
public:
    void flatten(TreeNode *root){
    }
};

前序遍历二叉树,将节点指针 push进入vector,顺序遍历vector中的节点,链接相邻 两节点,形成链单链表。(投机取巧) 该方法虽然可通过题目,但不满足就地(in-place)转换的条件。 若就地(in-place)转换应该如何做?

方法1 使用 vector
#include<vector>
public:
    void flatten(TreeNode *root){
        std::vector<TreeNode *> node_vec;
        preorder(root, node_vec);
        for(int i =1; i< node_vec.size(); i++){
            node_vec[i-1]->left = NULL;
            node_vac[i-1]->right = node_vec[i];
            
        }
private:
      void preorder(TreeNode *node, std::vector<TreeNode*> &node_vec){
      if(!node){
          return;
      }
      node_vec.push_back(node);
      preorder(node->left, node_vec);
      preorder(node->right,node_vec);
      }
    }

方法二:算法设计 将node指向的节点转为单链表,即将左子树left转为单链表,记录左子树最后一个节点 指针 left_last,将右子树right转换为单链表,记录右子树最后一个节点指针right_last,最终node 节点与左子树相连,left_last与right相连,函数要将right_last指针传出。

备份node->left指针、node->right指针,存储至left、right,设置存储左子树最后一个节点 指针left_last,存储右子树最后一个节点指针right_last,存储node节点为根的子树最后一个节点指针last。 如果左指针不空: 递归将左子树 拉直,并计算 left_last,node->left附空, node->right赋值 left,last赋值为 left_last; 如果右指针不空: 递归将右子树 拉直,并计算 right_last,左子树最后一个节点与右子树 相连,last赋值为 right_last。

class Solution{
public:
    void flatten(TreeNode *root){
        TreeNode * last = NULL;
        preorder(root,last);
    }
private:
    void preorder(TreeNode *node,TreeNode *&last){
         if(!node){
          return;
          }
          if(!node->left && !node->right){
          last = node;
          return;
          }
          TreeNode *left = node->left;//备份左右指针
          TreeNode *right = node->right;
          TreeNode *left_last = NULL;
          TreeNode *right_last = NULL;//左右子树最后一个节点
          if(left){
              preorder(left, left_last);// 
              node->left = NULL;
              node->right = left;
              last = left_last;
          }
          if(right){
              preorder(right, right_last);
              if(left_last){
                  left_last->right = right;
              }
              last = right_last;
          }
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • SPINNING单车你需要知道的一些事(二)能量区间

    随着可穿戴运动设备的普及化,运动变得越来越清晰和可视化。其中最重要的莫过于基于心率的练习,当然在单车中也不例外。以下两张图向我们展示了每个人的心率百分比,可以说...

    小飞侠xp
  • 二叉树基础知识

    树是n(n>=0)个节点的有限集,且这些节点满足如下关系: (1)有且仅有一个节点没有父结点,该节点称为树的根。 (2)除根外,其余的每个节点都有且仅有一个...

    小飞侠xp
  • 卷积神经网络-目标检测

    其中,bx、by表示汽车中点,bh、bw分别表示定位框的高和宽。以图片左上角为(0,0),以右下角为(1,1),这些数字均为位置或长度所在图片的比例大小。

    小飞侠xp
  • Leetcode 101. Symmetric Tree

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • 一天一大 lee(翻转二叉树)难度:简单-Day20200916

    用户6549452
  • 做出这道题,说明你很有机会进入 Google

    先来看递归的方法,写法非常简洁,只需要五行代码搞定:交换当前左右节点,然后直接调用递归即可 。

    五分钟学算法
  • Linux vim批量加注释

    背景: 最近在linux下配置邮件服务, 遇到一个问题如何批量注释多行, 我找到一个很好的解决方法,学会此方法,效率提高不只一点点啊.

    蛋未明
  • (cljs/run-at (JSVM. :all) "细说函数")

    前言  作为一门函数式编程语言,深入了解函数的定义和使用自然是十分重要的事情,下面我们一起来学习吧! 3种基础定义方法 defn 定义语法 (defn name...

    ^_^肥仔John
  • Docker实战(二):制作自己的Docker镜像

    使用 docker commit 来扩展一个镜像比较简单,但是不方便在一个团队中分享。我们可以使用 docker build 来创建一个新的镜像。为此,首先需要...

    拓荒者
  • (cljs/run-at (JSVM. :all) "细说函数")

    ^_^肥仔John

扫码关注云+社区

领取腾讯云代金券