LeetCode 训练场：226. 翻转二叉树

1. 题目

226. 翻转二叉树

2. 描述

翻转一棵二叉树。 示例： 输入： ​ 4 / \ 2 7 / \ / \ 1 3 6 9 输出： ​ 4 / \ 7 2 / \ / \ 9 6 3 1

3. 实现方法

3.1 方法 1

3.1.1 思路

1. 利用递归思想
2. 先判断根节点是否为 null，是则返回 null；
3. 定义一个中间变量 tmp ，然后递归交换左右子节点即可；
4. 由于主要进行的是交换操作，但是需要遍历整个树，所以时间复杂度为

；

3.1.2 实现

public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }

    TreeNode tmp = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(tmp);
    return root;
}