二叉树转链表

给定一个二叉树,将该二叉树 就地(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 条评论
登录 后参与评论

相关文章

来自专栏尾尾部落

[剑指offer] 二叉树的镜像

通过对以上两棵树的观察,我们可以总结出这两棵树的根节点相同,但它们的左、右两个子节点交换了位置。所以我们可以得出求一棵树的镜像的过程:先前序遍历这棵树的每个节点...

1472
来自专栏静默虚空的博客

单链表的算法

要点 在顺序表的算法文章中,我们讨论了线性表的顺序存储结构——顺序表。 顺序表是用一组地址连续的存储单元来保存数据的,所以它具有随机存取的特点。即查找快速,但是...

2099
来自专栏算法修养

HOJ 2148&POJ 2680(DP递推,加大数运算)

Computer Transformation Time Limit: 1000MS Memory Limit: 65536K Total S...

29712
来自专栏武培轩的专栏

剑指Offer-二叉搜索树的第k个结点

题目描述 给定一颗二叉搜索树,请找出其中的第k大的结点。例如, 5 /  3 7 / / 2 4 6 8 中,按结点数值大小顺序第三个结点的值为4。 思路 利用...

3297
来自专栏Jack-Cui

111.Minimum Depth of Binary Tree(Tree-Easy)

Given a binary tree, find its minimum depth. The minimum depth is the number of ...

2179
来自专栏武培轩的专栏

剑指Offer-从上往下打印二叉树

题目描述 从上往下打印出二叉树的每个节点,同层节点从左至右打印。 思路 使用两个队列一个存放节点,一个存放值。先将根节点加入到队列中,然后遍历队列中的元素,遍历...

2827
来自专栏Java Web

数据结构与算法(3)——树(二叉、二叉搜索树)树LeetCode相关题目整理

树是一种类似于链表的数据结构,不过链表的结点是以线性方式简单地指向其后继结点,而树的一个结点可以指向许多个结点;数是一种典型的非线性结构;树结构是以表达具有层次...

2262
来自专栏desperate633

LeetCode 144. Binary Tree Preorder Traversal题目分析代码

Given a binary tree, return the preorder traversal of its nodes' values. For ex...

992
来自专栏LeetCode

LeetCode 102 & 103 &107 & 637. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie,...

1010
来自专栏赵俊的Java专栏

排序链表转换为二分查找树

2195

扫码关注云+社区

领取腾讯云代金券