226. Invert Binary Tree

題目

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

Input: root = [4,2,7,1,3,6,9] Output: [4,7,2,9,6,3,1]

Example 2:

Input: root = [2,1,3] Output: [2,3,1] Example 3:

Input: root = [] Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

題目大意

反轉二叉樹

解題思路

用遞歸來解決,先遞歸調用反轉根節點的左children,然後遞歸調用反轉根節點的右children,然後左右交換根節點的左children和右children。 有點像是BFS

BFS(廣度優先搜索)則使用隊列(Queue)來實現。在BFS中,您首先處理一個節點,然後將其子節點按某種順序排隊,接著繼續處理隊列的前端節點,直到隊列為空。

來源

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0226.Invert-Binary-Tree/main.go

package invertbinarytree

import (
    "LeetcodeGolang/Utility/structures"
)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

// type TreeNode struct {
//     Val   int
//     Left  *TreeNode
//     Right *TreeNode
// }

func InvertTree(root *structures.TreeNode) *structures.TreeNode {
    if root == nil {
        return nil
    }

    InvertTree(root.Left)
    InvertTree(root.Right)

    root.Left, root.Right = root.Right, root.Left
    return root
}

func InvertTree2(root *structures.TreeNode) *structures.TreeNode {

    if root != nil {
        root.Left, root.Right = InvertTree2(root.Right), InvertTree2(root.Left)
    }

    return root
}

func InvertTree3(root *structures.TreeNode) *structures.TreeNode {
    queue := make([]*structures.TreeNode, 0)
    queue = append(queue, root)

    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]

        current.Left, current.Right = current.Right, current.Left

        if current.Left != nil {
            queue = append(queue, current.Left)
        }

        if current.Right != nil {
            queue = append(queue, current.Right)
        }
    }
    return root
}
func BuildTree(nums []int, index int) *TreeNode {
    if index >= len(nums) || nums[index] == -1 {
        return nil
    }
    root := &TreeNode{Val: nums[index]}
    root.Left = BuildTree(nums, 2*index+1)
    root.Right = BuildTree(nums, 2*index+2)
    return root
}

func IntsToTree(nums []int) *TreeNode {
    return BuildTree(nums, 0)
}

Benchmark

goos: darwin
goarch: amd64
pkg: LeetcodeGolang/Leetcode/0226.Invert-Binary-Tree
cpu: Intel(R) Core(TM) i5-8259U CPU @ 2.30GHz
BenchmarkInvertTree-8            2533011               398.7 ns/op           168 B/op          7 allocs/op
BenchmarkInvertTree2-8           2667645               392.4 ns/op           168 B/op          7 allocs/op
BenchmarkInvertTree3-8           1403001               727.5 ns/op           296 B/op         13 allocs/op
PASS
ok      LeetcodeGolang/Leetcode/0226.Invert-Binary-Tree 4.889s
© Kimi Tsai all right reserved.            Updated : 2024-05-06 09:36:37

results matching ""

    No results matching ""