本文共 1390 字，大约阅读时间需要 4 分钟。

题目：114. 二叉树展开为链表

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

例如，给定二叉树

1   / \  2   5 / \   \3   4   6

将其展开为：

1 \  2   \    3     \      4       \        5         \          6

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

利用分治法思想递归法求解。

1. divide

   将原始二叉树分为三个部分：根节点root，左子树和右子树。

2. conquer

   递归地将左子树和右子树拉平，执行flatten(左子树)，flatten(右子树)。

3. combine

   将root的右子树接到左子树下方，然后将整个左子树作为右子树。

代码

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {
   public:    void flatten(TreeNode* root) {
           if (!root) {
               return;        }        flatten(root->left);        flatten(root->right);        TreeNode* left = root->left;        TreeNode* right = root->right;        //找到左子树的最后节点last        TreeNode* next = left;        TreeNode* last = nullptr;        while (next) {
               last = next;            next = next->right;        }        //将右子树拼接到左子树的最后        if (last) {
               last->right = right;        } else {
               left = right;        }        root->left = nullptr;        root->right = left;    }};