LeetCode 226. 翻转二叉树

226. 翻转二叉树

翻转一棵二叉树。

示例:

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

备注:

• 谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/invert-binary-tree/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

• 创建二叉搜索树

public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

• 1. 递归法

思路：

1. 递归终止条件为当前根节点为 null
2. 使用递归依次将左右子树都进行翻转
3. 最后将翻转后的结果交换位置添加到左（右）子树中即可

public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode leftNode = root.left;
        TreeNode rightNode = root.right;
        root.left = invertTree(rightNode);
        root.right = invertTree(leftNode);
        return root;
    }

复杂度分析：

• 时间复杂度：O(n), 需要遍历每个元素

• 空间复杂度：O(n),使用了递归，在最坏情况下栈内需要存放 O(h) 个方法调用，其中 h 是树的高度。可得出空间复杂度为 O(n)。

• 2. 迭代法

思路：

1. 创建一个队列，并将根节点放入队列中
2. 只要队列不为 null，取出队首元素，交换其左右子树
3. 再将当前节点的左右子树添加到队列中即可

public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            TreeNode temp = cur.left;
            cur.left = cur.right;
            cur.right = temp;
            if (cur.left != null) queue.add(cur.left);
            if (cur.right != null) queue.add(cur.right);
        }
        return root;
    }

复杂度分析：

• 时间复杂度：O(n), 需要遍历每个元素将其添加到队列
• 空间复杂度：O(n), 队列中添加每个元素所占用的空间

---

• 源码

• 我会每天更新新的算法，并尽可能尝试不同解法，如果发现问题请指正

• Github