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

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;
        }
    }
};