LeetCodeHOT100——114.二叉树展开为链表-创新互联

给你二叉树的根结点 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元起，快前往官网查看详情吧