
问题
翻转一棵二叉树。
输入:
4
/ \
2 7
/ \ / \
1 3 6 9
输出:
4
/ \
7 2
/ \ / \
9 6 3 1
备注:这个问题是受到 Max Howell 的 原问题 启发的 :
谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板上写出翻转二叉树这道题,这太糟糕了。
Invert a binary tree.
Input:
4
/ \
2 7
/ \ / \
1 3 6 9
Output:
4
/ \
7 2
/ \ / \
9 6 3 1
Trivia:This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.
示例
public class Program { public static void Main(string[] args) { var root = new TreeNode(1) { left = new TreeNode(3) { left = new TreeNode(5), right = new TreeNode(7) }, right = new TreeNode(9) }; var res = InvertTree(root); ShowTree(res); Console.WriteLine(); root = new TreeNode(2) { left = new TreeNode(4) { left = new TreeNode(6) }, right = new TreeNode(8) }; res = InvertTree2(root); ShowTree(res); Console.ReadKey(); } public static void ShowTree(TreeNode node) { if(node == null) { Console.Write("null "); return; } Console.Write($"{node.val} "); ShowTree(node.left); ShowTree(node.right); } public static TreeNode InvertTree(TreeNode root) { PreOrder(root); return root; } public static void PreOrder(TreeNode root) { if(root == null) return; var swap = root.left; root.left = root.right; root.right = swap; PreOrder(root?.left); PreOrder(root?.right); } public static TreeNode InvertTree2(TreeNode root) { if(root == null) return null; var swap = root.left; root.left = InvertTree2(root.right); root.right = InvertTree2(swap); return root; } public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; } } }
以上给出2种算法实现,以下是这个案例的输出结果:
1 9 null null 3 7 null null 5 null null 2 8 null null 4 null 6 null null
分析:
显而易见,以上2种算法的时间复杂度均为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4080。