二叉树展开为链表

问题描述

给定一个二叉树，原地将它展开为链表。

例如，给定二叉树

   1
   / \
  2   5
 / \   \
3   4   6

将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list

思路

题目描述中是将二叉树展开为链表，但是函数返回值是void，所以题目真实的要求应该是将一个二叉树按中序遍历的顺序展开为一个只有右子树的二叉树。

• 将二叉树按照中序遍历的顺序存储到一个vector<TreeNode*>中。
• TreeNode *p=root,即从root所在的节点开始，其左子树为nullptr，右子树为vec[i]（注意i是从1开始的），然后，p=p->right

题解

class Solution {
public:
    vector<TreeNode*> vec;
    void flatten(TreeNode* root) {
        TreeNode *p=root;
        dfs(root);
        for(int i=1;i<vec.size();i++){
            p->left= nullptr;
            p->right=vec[i];
            p=p->right;
        }
   }
   void dfs(TreeNode *node){
        if(node== nullptr) return;
        vec.push_back(node);
        dfs(node->left);
        dfs(node->right);
    }
};