226. Invert Binary Tree
https://leetcode.com/problems/invert-binary-tree/
Easy
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
Problem
Swap all left and right nodes of the entire tree.
Approach
We can treat every node as a root node, traverse all root nodes, and swap each root’s left and right children.
- Check if root is nil — if so, end the traversal for this root node.
- Swap the current root’s left and right children.
- Treat the left and right children as roots and recursively call invertTree until step 1 terminates the traversal.
Source Code
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return root
}
root.Left, root.Right = root.Right, root.Left
invertTree(root.Left)
invertTree(root.Right)
return root
}
Closing
Do you have a better or simpler solution?
Feel free to leave a comment on my blog. Your feedback motivates me to keep writing. Thank you for reading, and let’s grow together to become better versions of ourselves.
