InvertBinaryTree [source code]

public class InvertBinaryTree {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode res = new TreeNode(root.val);
        res.left = invertTree(root.right);
        res.right = invertTree(root.left);
        return res;
    }
}

拿到一个问题, 先在最开始加一行:

// base case

用来提醒自己最后检查是否合理处置了 empty, null 这一类的base case;

这个问题不用急着刚开始就想, 这个就比较耽误时间, 而且干扰核心算法的思路; 而且假如是在面试, 那么面试官肯定是不愿意看你上来就搞这种 trivia 的;

总体来说是一个很简单的问题, 但是我还是 fail 了两次;
第一次是因为忘记了写 recursion: 感觉对 recursion 太熟悉也容易出问题; 看到一个 tree 就默认其干脆自带recursion 属性, 自己写代码的时候就忘记加 recursion 了;

另外一次是因为 recurse 加错了, 加在了 root 上面; 这个就很蠢了,没什么好说的;

速度是最优解;

Problem Description

Invert a binary tree.

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

to

     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 fuck off.
Difficulty:Easy
Category:Algorithms
Acceptance:51.31%
Contributor: LeetCode
Topics:
Tree

/**

• Definition for a binary tree node.
• public class TreeNode {
• int val;
• TreeNode left;
• TreeNode right;
• TreeNode(int x) { val = x; }
• }
  */