189 8069 5689
给你二叉树的根结点 root ，请你将它展开为一个单链表：
为成都等地区用户提供了全套网页设计制作服务，及成都网站建设行业解决方案。主营业务为成都网站建设、成都做网站、成都网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
将二叉树展开为单链表之后，单链表中的节点顺序即为二叉树的前序遍历访问各节点的顺序。
因此，可以对二叉树进行前序遍历，获得各节点被访问到的顺序。
由于将二叉树展开为链表之后会破坏二叉树的结构，因此在前序遍历结束之后更新每个节点的左右子节点的信息（比如不要忘了左结点置空），将二叉树展开为单链表。
前序遍历可以通过递归或者迭代的方式实现
一：递归法（调用系统的栈）
java代码如下：
class Solution{public void flatten(TreeNode root){Listlist = new ArrayList<>();
preorderTraversal(root,list);//前序遍历生成的列表
int size = list.size();//获取列表长度
for (int i = 1; i< size; i++) { TreeNode pre = list.get(i-1);//取前驱节点
TreeNode cur = list.get(i); //取当前节点
pre.left = null;//左子树置空
pre.right = cur;//右子树指向当前节点，实现链表的单向拼接
}
}
public void preorderTraversal(TreeNode root, Listlist) {//前序遍历：中→左→右
if (root != null) { list.add(root);//中 处理逻辑：添加节点
preorderTraversal(root.left, list);//左
preorderTraversal(root.right, list);//右
}
}
} 二、迭代法（手动维护一个栈）
java代码如下：
class Solution {public void flatten(TreeNode root){Listlist = new ArrayList<>();//用来存储前序遍历结果
Stackstack = new Stack<>();//用来前序遍历二叉树
TreeNode node = root;
while(node != null || !stack.isEmpty()){ while(node != null){//找到最左下的节点为止(即找到节点没有左孩子为止)
list.add(node);//加入节点到结果集中
stack.push(node);//节点入栈
node = node.left;
}
node = stack.pop();//出左下的节点
node = node.right;//继续查找左下节点的右孩子
}
//经过上面的循环之后，全部遍历所有节点
int size = list.size();
for(int i = 1; i< size; i++){ TreeNode pre = list.get(i-1);
TreeNode cur = list.get(i);
pre.left = null;//左子树置空
pre.right = cur;//右子树指向当前节点
}
}
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧