0114.Flatten-Binary-Tree-to-Linked-List test case wrong

[wizardpisces]

test case wrong

expect: [1 2 3 4 5 6] but received : [1 2 4 5 3 6]

[wizardpisces]

Reason:

Ints2TreeNode is not a preorder deserialization

Possible Solution:

0. rootOne := structures.Ints2TreeNode(p.one) 1. inputSlice := structures.Tree2Preorder(rootOne)
1. flatten(rootOne)
2. result := structures.Tree2Preorder(rootOne)

then compare inputSlice with result

[Don2025]

Hello! : ) Sorry to have kept you waiting. I've solved this problem and push a commit. structures/TreeNode.go

// Strings2TreeNode converts []string to *TreeNode
func Strings2TreeNode(strs []string) *TreeNode {
    n := len(strs)
    if n == 0 {
        return nil
    }
    x, _ := strconv.Atoi(strs[0])
    root := &TreeNode{Val: x}
    queue := make([]*TreeNode, 1, n<<1)
    queue[0] = root
    i := 1
    for i < n {
        node := queue[0]
        queue = queue[1:]
        if i < n && strs[i] != "null" {
            x, _ = strconv.Atoi(strs[i])
            node.Left = &TreeNode{Val: x}
            queue = append(queue, node.Left)
        }
        i++
        if i < n && strs[i] != "null" {
            x, _ = strconv.Atoi(strs[i])
            node.Right = &TreeNode{Val: x}
            queue = append(queue, node.Right)
        }
        i++
    }
    return root
}

// Tree2LevelOrderStrings converts *TreeNode into []string by level order traversal.
func Tree2LevelOrderStrings(root *TreeNode) []string {
    var ans []string
    if root == nil {
        return ans
    }
    queue := []*TreeNode{root}
    var level int
    for level = 0; len(queue) > 0; level++ {
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[i]
            if node == nil {
                ans = append(ans, "null")
            } else {
                ans = append(ans, strconv.Itoa(node.Val))
                if node.Left != nil || node.Right != nil {
                    queue = append(queue, node.Left, node.Right)
                }
            }
        }
        queue = queue[size:]
    }
    level--
    return ans
}

114. Flatten Binary Tree to Linked List_test.go

     func Test_Problem114(t *testing.T) {
     
     qs := []question114{
     
         {
             para114{[]string{"1", "2", "5", "3", "4", "null", "6"}},
             ans114{[]string{"1", "null", "2", "null", "3", "null", "4", "null", "5", "null", "6"}},
         },
     
         {
             para114{[]string{"0"}},
             ans114{[]string{"0"}},
         },
     
         {
             para114{[]string{"1", "2", "3", "4", "5", "6"}},
             ans114{[]string{"1", "null", "2", "null", "3", "null", "4", "null", "5", "null", "6"}},
         },
     }
     
     fmt.Printf("------------------------Leetcode Problem 114------------------------\n")
     
     for _, q := range qs {
         _, p := q.ans114, q.para114
         fmt.Printf("【input】:%v       \n", p)
         rootOne := structures.Strings2TreeNode(p.one)
         flatten(rootOne)
         fmt.Printf("【output】:%v      \n", structures.Tree2LevelOrderStrings(rootOne))
     }
     fmt.Printf("\n\n\n")
     }

     The following is the output of go test under Windows system:

     
     D:\Code\LeetCode-Go\leetcode\0114.Flatten-Binary-Tree-to-Linked-List>go test
     ------------------------Leetcode Problem 114------------------------
     【input】:{[1 2 5 3 4 null 6]}
     【output】:[1 null 2 null 3 null 4 null 5 null 6]
     【input】:{[0]}
     【output】:[0]
     【input】:{[1 2 3 4 5 6]}
     【output】:[1 null 2 null 4 null 5 null 3 null 6]

PASS ok github.com/halfrost/LeetCode-Go/leetcode/0114.Flatten-Binary-Tree-to-Linked-List 0.139s

[wizardpisces]

Still not matched...

Assertion may help avoid this kind of negligence?

[Don2025]

I'm stupid, because I outputed the levelorder traversal rather than preorder traversal in test.go. But look this draft when you input [1, 2, 3, 4, 5, 6], the expected output should be [1, 2, 4, 5, 3, 6]. Read the problem description carefully please!

[halfrost]

@Don2025 Thanks