首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >二叉树转链表

二叉树转链表

作者头像
小飞侠xp
发布2018-08-29 11:21:41
7470
发布2018-08-29 11:21:41
举报

给定一个二叉树,将该二叉树 就地(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;
          }
    }
};
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018.05.02 ,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 方法1 使用 vector
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档