package leetcode import ( "github.com/halfrost/LeetCode-Go/structures" ) // TreeNode define type TreeNode = structures.TreeNode /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ // 解法一 非递归 func flatten(root *TreeNode) { list, cur := []int{}, &TreeNode{} preorder(root, &list) cur = root for i := 1; i < len(list); i++ { cur.Left = nil cur.Right = &TreeNode{Val: list[i], Left: nil, Right: nil} cur = cur.Right } return } func preorder(root *TreeNode, output *[]int) { if root != nil { *output = append(*output, root.Val) preorder(root.Left, output) preorder(root.Right, output) } } // 解法二 递归 func flatten1(root *TreeNode) { if root == nil || (root.Left == nil && root.Right == nil) { return } flatten(root.Left) flatten(root.Right) currRight := root.Right root.Right = root.Left root.Left = nil for root.Right != nil { root = root.Right } root.Right = currRight } // 解法三 递归 func flatten2(root *TreeNode) { if root == nil { return } flatten(root.Right) if root.Left == nil { return } flatten(root.Left) p := root.Left for p.Right != nil { p = p.Right } p.Right = root.Right root.Right = root.Left root.Left = nil }