226. Invert Binary Tree 翻转二叉树

［抄题］：

Invert a binary tree.

     4
   /   
  2     7
 /    / 
1   3 6   9

     4
   /   
  7     2
 /    / 
9   6 3   1

[暴力解法]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

以为要分为r.r = l.l, r.l = l.r来讨论，但是其实这样只能最后判断相等。翻转是每一步都要进行的动作，应该尽早开始

［一句话思路］：

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

ab交换在二叉树中的对应情况就是翻转

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［关键模板化代码］：

［其他解法］：

bfs, stack

［Follow Up］：

［LC给出的题目变变变］：

对称二叉树 · symmetric binary tree

不知道有什么数学规律的时候，分情况讨论：分左右两边

[代码风格] ：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode temp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(temp);
        return root;
    }
}

View Code