114. Flatten Binary Tree to Linked List二叉树转链表

qlmx
qlmx
qlmx
54
文章
2
评论
2020年2月15日00:11:18 评论 900阅读4分10秒

114. Flatten Binary Tree to Linked List(二叉树转链表)

1.问题描述

Given a binary tree, flatten it to a linked list in-place.

给定一个二叉树,将该二叉树 就地(in-place)转换为单链表。单链表中节点顺序为二叉树前序遍历顺序。

For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

2.C++实现1(基于vector,此方法不是接地转换)

//方法一使用前序遍历,将值存在vector中
class Solution {
public:
    void flatten(TreeNode* root) {
        vector<TreeNode*> result;
        preorder(root, result);

        for(int i=1; i<result.size(); i++) {
            result[i-1]->left = NULL;
            result[i-1]->right = result[i];
        }

    }

private:
    void preorder(TreeNode* node, vector<TreeNode*> &res) {
        if(!node)
            return;
        res.push_back(node);
        preorder(node->left, res);
        preorder(node->right, res);
    }
};

3.C++实现2

//将node指向的节点转为单链表,即将左子树left转为单链表,记录左子树最后一个节点 指针
// left_last,将右子树right转换为单链表,记录右子树最后一个节点指针right_last,
// 最终node 节点与左子树相连,left_last与right相连,函数要将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;
        }
    }
};
继续阅读
  • 我的微信小程序
  • 这是我的微信小程序扫一扫
  • weinxin
  • 我的微信公众号
  • 我的微信公众号扫一扫
  • weinxin
qlmx
  • 本文由 发表于 2020年2月15日00:11:18
  • 除非特殊声明,本站文章均为原创,转载请务必保留本文链接
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: