力扣题解-114. 二叉树展开为链表（分治法思想，递归的方式求解）

本文主要是介绍力扣题解-114. 二叉树展开为链表（分治法思想，递归的方式求解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

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

divide
将原始二叉树分为三个部分：根节点root，左子树和右子树。
conquer
递归地将左子树和右子树拉平，执行flatten(左子树)，flatten(右子树)。
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;//找到左子树的最后节点lastTreeNode* 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;}
};