长大后想做什么？做回小孩！

0%

LeetCode——翻转二叉树

发表于 分类于 Valine：
本文字数： 303

NO.141 环形链表 简单

tPs8ts.png

震惊！著名软件 Homebrew 的作者 Max Howell 在 面试 Google 被拒，竟然是因为不会这个！

tPyvM6.png

Google：我们 90% 的工程师都用你写的软件（Homebrew），但你没法在白板上翻转二叉树，所以滚蛋吧

思路一：深度优先遍历 从根节点开始，交换左右子树，然后递归的交换左右子树的左右子树。终止条件是子树节点为空。

1
2
3
4
5
6
7
8
9
10
11
12
public TreeNode invertTree(TreeNode root) {
    //节点为空终止
    if (root ==null) return root;
    //交换根节点的左右子树
    TreeNode temp = root.right;
    root.right = root.left;
    root.left = temp;
    //分别交换左右子树的左右子树
    invertTree(root.right);
    invertTree(root.left);
    return root;
}

时间复杂度：O(n) 空间复杂度：O(h) h 是树高

思路二：广度优先遍历 广搜二叉树，并且遍历过程中交换树中所有节点的左子树和右子树 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            //交换左右子树
            TreeNode temp = poll.right;
            poll.right = poll.left;
            poll.left = temp;
            //左右子树不空，则入队
            if (poll.left != null) queue.offer(poll.left);
            if (poll.right != null) queue.offer(poll.right);
        }
        return root;
    }

时间复杂度：O(n) 空间复杂度：O(w) 树的最大宽度 w

本人菜鸟，有错误请告知，感激不尽！

更多题解源码和学习笔记：github 、CSDN 、M1ng