226 Invert Binary Tree
Invert a binary tree.
4
/ \
2 7
/ \ / \
1 3 6 9
to
4
/ \
7 2
/ \ / \
9 6 3 1
void swap(TreeNode *&a, TreeNode *&b) {
TreeNode *temp = a;
a = b;
b = temp;
}
TreeNode* invertTree(TreeNode* root) {
if (!root) return NULL;
queue<TreeNode*> q;
q.push(root);
while(!q.empty())
{
TreeNode* node = q.front();
q.pop();
swap(node->left, node->right);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
return root;
}
The Idea: Follow a level order traversal and swap left and right child nodes. Consider the tree with just a left and right child. The solution would be to simple swap the children. Note that we are swapping the addresses, and not the values of the nodes. This ensure that the entirety of the left side of the tree becomes the right side of the tree all together. In otherwords, we are swapping subtrees.
Complexity: O(n) time and space
DFS Approach
TreeNode* invertTree(TreeNode* root) {
if (!root) return nullptr;
TreeNode *temp = root->left;
root->left = invertTree(root->right);
root->right = invertTree(temp);
return root;
}
- The idea is the same (we perform a swap on each child for each parent node. In the end, we have to be comfortable with three things. The first, is that we create N temporary Nodes, each of which have their unique local stack frame. Secondly, we move down the trees right child continuously until we hit
null. So the first real swap will be a swap of nullptrs. However, when we return twice, the root will be2androot->leftwill have access toroot->right, and vise-versa because of the temporary variable.
Python Solution
import queue
class Solution:
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
q = queue.Queue()
if root:
q.put(root)
while not q.empty():
front = q.get()
front.left, front.right = front.right, front.left
if front.left:
q.put(front.left)
if front.right:
q.put(front.right)
return root
Last modified 4yr ago