How to Mirror a Binary Tree?

  • 时间:2020-10-12 15:56:23
  • 分类:网络文摘
  • 阅读:177 次

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) —

推荐阅读:
摸黄球白球可能性的问题  如果要准时到达需要多少小时  货物的原价是多少元  用去水泥和沙子各多少吨  求AB两站距离的问题  如图小正方形的边长为5cm求阴影部分的面积  全天计划生产消毒药水多少瓶  等候上菜和用餐的时间总和最少是多少  在一次环保知识竞赛中  原上的草、人、蒙古包 
评论列表
添加评论