[Leetcode]28.二叉树展开为链表

题目:给你二叉树的根结点 root ，请你将它展开为一个单链表：
    展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
    展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [0]
输出：[0]

思想一: 寻找前驱结点,我们发现在前序遍历的时候,在遍历右子树前最后一个遍历的是左子树的最右结点,我们只需要把右子树放到左子树的最右结点的右边,再进行当前结点的左右子树交换,即可实现二叉树的展开。

每次判断结点是否有左节点,如果没有,则已经是排序好的了,再判断他的右节点即可。如果有，那么找他的左孩子的子树的最右结点，找到后把这个结点的右子树指向当前结点的右子树，然后把当前结点的右子树指向左子树，左子树指空。结束条件是向右遍历结束

func flatten(root *TreeNode) {
	cur :=root
	for cur !=nil{
		if cur.Left!=nil{
			next:=cur.Left
			pre := next
			for pre.Right!=nil{
				pre = pre.Right
			}
			pre.Right = cur.Right
			cur.Right = cur.Left
			cur.Left = nil
		}
		cur = cur.Right
	}
}

 思想二:通过上一层的next来解决下层的连接问题。每层的起始结点设置为最左的那个结点。实际上在添加Next结点的时候,会出现两种情况,第一种是父节点的左孩子指向右孩子,这种直接node.Left.Next = node.Right即可,第二种是父节点的右孩子指向父节点的右兄弟的左孩子,这种就需要通过父节点的Next结点的Left来定位,node.Right.Next = node.next.Left,判定条件是父节点是否有Next指向。

func connect(root *Node) *Node {
	if root == nil{
		return root
	}
	for leftmost:=root;leftmost!=nil;leftmost = leftmost.Left{
		for node:=leftmost;node!=nil;node= node.Next{
			node.Left.Next = node.Right
			if node.Next!=nil{
				node.Right.Next = node.next.Left
			}
		}
	}
	return root
}

题目来源：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list