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求阴影部分的面积 全天计划生产消毒药水多少瓶 等候上菜和用餐的时间总和最少是多少 在一次环保知识竞赛中 原上的草、人、蒙古包
- 评论列表
-
- 添加评论