This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.Invert a binary tree.
Example:Input:
4 / \ 2 7 / \ / \ 1 3 6 9Output:
4 / \ 7 2 / \ / \ 9 6 3 1
GoLang Implementation of Inverting a Binary Tree
Inverting Binary Tree can be done efficiently using Recursion. We recursively invert the left and right trees and then swap them. We can also swap and then invert – which will work as well.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func invertTree(root *TreeNode) *TreeNode { if root == nil { return nil } var left = invertTree(root.Left) var right = invertTree(root.Right) root.Left = right root.Right = left return root } |
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func invertTree(root *TreeNode) *TreeNode { if root == nil { return nil } var left = invertTree(root.Left) var right = invertTree(root.Right) root.Left = right root.Right = left return root }
GoLang supports the Tuple assignment meaning that we can write this a bit cleaner/shorter.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func invertTree(root *TreeNode) *TreeNode { if root != nil { root.Left, root.Right = invertTree(root.Right), invertTree(root.Left) } return root } |
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func invertTree(root *TreeNode) *TreeNode { if root != nil { root.Left, root.Right = invertTree(root.Right), invertTree(root.Left) } return root }
See also other posts on inverting the binary tree:
- Teaching Kids Programming – Recursive Algorithm to Invert a Binary Tree
- How to Invert a Binary Tree in C/C++?
- Invert a Binary Tree using GoLang
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
409 wordsloading...
Last Post: Teaching Kids Programming - Dynamic Programming Algorithm to Compute Minimum Number of Coins
Next Post: Teaching Kids Programming - Minimum Number of Operations to Target Number