Question
Formatted question description: https://leetcode.ca/all/226.html
226 Invert Binary Tree
Invert a binary tree.
Example:
Input:
4
/ \
2 7
/ \ / \
1 3 6 9
Output:
4
/ \
7 2
/ \ / \
9 6 3 1
Trivia:
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.
@tag-tree
Algorithm
Exchange the current left and right nodes, and call recursion directly.
Code
Java
-
import java.util.Stack; public class Invert_Binary_Tree { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) { return root; } // bfs Stack<TreeNode> sk = new Stack<>(); sk.push(root); while (!sk.isEmpty()) { TreeNode current = sk.pop(); if (current.left != null) { sk.push(current.left); } if (current.right != null) { sk.push(current.right); } // switch TreeNode tmp; tmp = current.left; current.left = current.right; current.right = tmp; } return root; } } class Solution_recursion { public TreeNode invertTree(TreeNode root) { if (root == null) { return root; } // swap TreeNode tmp = root.left; root.left = root.right; root.right = tmp; invertTree(root.left); invertTree(root.right); return root; } } }
-
// OJ: https://leetcode.com/problems/invert-binary-tree/ // Time: O(N) // Space: O(H) class Solution { public: TreeNode* invertTree(TreeNode* root) { if (!root) return NULL; swap(root->left, root->right); invertTree(root->left); invertTree(root->right); return root; } };
-
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def invertTree(self, root): """ :type root: TreeNode :rtype: TreeNode """ if not root: return root.left, root.right = root.right, root.left self.invertTree(root.left) self.invertTree(root.right) return root