Given a binary tree like this:
8 / \ 6 10 / \ / \ 5 7 9 11
Your task is to mirror it which becomes this:
8 / \ 10 6 / \ / \ 11 9 7 5
The most elegant algorithm to mirror a binary tree is using recursion. We can recursively mirror left and right trees respectively and then swap the left and right trees.
1 2 3 4 5 6 7 8 9 10 11 12 13 | public class Solution { public void Mirror(TreeNode root) { if (root == null) return; // make left tree also a mirror recursively Mirror(root.left); // make right tree also a mirror tree. Mirror(root.right); // swap left and right trees TreeNode t = root.left; root.left = root.right; root.right = t; } } |
public class Solution { public void Mirror(TreeNode root) { if (root == null) return; // make left tree also a mirror recursively Mirror(root.left); // make right tree also a mirror tree. Mirror(root.right); // swap left and right trees TreeNode t = root.left; root.left = root.right; root.right = t; } }
The time complexity is O(N) where each node will be visited constant time, and the space complexity through calling stacks via recursion is O(N)=O(h) which is the height of the tree.
It is said that this is one of the Google’s interview question, a simple one though.
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
227 wordsloading...
Last Post: How to Find the Kth Smallest Element in a BST Tree Using Java/C++?
Next Post: Algorithms: How to Find N-Repeated Element in Size 2N Array?