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)$ 。

巴特西

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

最新文章

热门文章