114. Flatten Binary Tree to Linked List

题目

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

The flattened tree should look like:

题意

给定一个二叉树，将其平摊为单边的链表。

题解

使用前序遍历，对每一个子节点将其左边赋值为nil，然后将左子树放置在右边，再将原本的右子树接在当前右边的尾部。

代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode)  {
    Preorder(root)
}

func Preorder(root *TreeNode)*TreeNode{
    if root==nil{
        return nil
    }
    
    left := Preorder(root.Left)
    right := Preorder(root.Right)
    
    root.Left = nil
    root.Right = left
    p := root.Right
    if p!=nil{
       for p.Right!=nil{
          p = p.Right
       }
        p.Right = right 
    }else{
        root.Right=right
    }

    return root
}