C#LeetCode刷题之#226-翻转二叉树(Invert Binary Tree)

C#LeetCode刷题之#226-翻转二叉树(Invert Binary Tree)

问题

翻转一棵二叉树。

输入:

     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种算法的时间复杂度均为: O(n)​ 。

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/4080

发表评论

登录后才能评论