思路：深度优先搜索dfs+链表，时间复杂度0(n)。

C++版本：

/*** 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:TreeNode* dfs(TreeNode* root) {if(root==nullptr) return root;TreeNode * Left=dfs(root->left);TreeNode * Right=dfs(root->right);root->left=nullptr;if(Left==nullptr){root->right=Right;return root;}root->right=Left;// 让左子树的最后一个节点去连接RightTreeNode *cur=Left;while(cur->right!=nullptr){cur=cur->right;}cur->right=Right;return root;}void flatten(TreeNode* root) {dfs(root);}
};

JAVA版本：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {TreeNode dfs(TreeNode root) {if(root==null) return root;TreeNode Left=dfs(root.left);TreeNode Right=dfs(root.right);root.left=null;if(Left==null){root.right=Right;return root;}root.right=Left;TreeNode cur=Left;while(cur.right!=null){cur=cur.right;}cur.right=Right;return root;}public void flatten(TreeNode root) {dfs(root);}
}

GO版本：

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func flatten(root *TreeNode)  {dfs(root)
}
func dfs(root *TreeNode) *TreeNode {if root==nil {return root}Left:=dfs(root.Left)Right:=dfs(root.Right)root.Left=nilif Left==nil {root.Right=Rightreturn root}root.Right=Left;cur:=Leftfor cur.Right!=nil {cur=cur.Right}cur.Right=Rightreturn root
}