TechNomads

题目

给定一个二叉树，原地将它展开为一个单链表。

 

例如，给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6
将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

解法-递归

题目要求原地展开，故不能使用数组类变量存储全部节点值再重构树。将左右子树分别递归展开，将原左子树变为节点的右子树，再将原右子树变为当前右子树最右节点的右子树。

go代码实现

func flatten(root *TreeNode)  {

	if root == nil {
		return
	}

	flat(root)
}

func flat(node *TreeNode) {

	if node == nil {
		return
	}

	flat(node.Left)
	flat(node.Right)

	var temp *TreeNode = node.Right

	node.Right, node.Left = node.Left, nil

	for node.Right != nil {
		node = node.Right
	}
	node.Right = temp

}

或者简化一下代码：

func flatten(root *TreeNode)  {

	if root == nil {
		return
	}

	flat(root.Left)
	flat(root.Right)

	var temp *TreeNode = root.Right

	root.Right, root.Left = root.Left, nil

	for root.Right != nil {
		root = root.Right
	}
	root.Right = temp
}