How to Mirror a Binary Tree?

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

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

推荐阅读:
保健食品虚假广告花样百出太坑人  冰淇淋为何要加如此多的食品添加剂  肉禽类的这些部位千万不要去吃  百事可乐配方含致癌色素仍坚称安全  调查称槟榔是一级致癌物可引发口腔癌  嚼食槟榔对身体健康的危害非常大  槟榔被认定为一级致癌物可引发口腔癌  食品安全监管工作的有效性令人疑惑  厂家称没法根本解决五芳斋粽子发霉  饮食保健:盘点枸杞的十大养生功效 
评论列表
添加评论