博客

226. Invert Binary Tree

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.

226.翻转二叉树

把一棵二叉树翻转（如图）

冷知识：

这个问题启迪于Max Howell的这个推文

谷歌：虽然我们90%的工程师用你写的软件(Homebrew)，但你却不能在一却白板上翻转一个二叉树，所以滚蛋吧。

（Homebrew是Mac平台上的软件包管理器，作者是Max Howell,但Max Howell被谷歌拒绝聘用，原因是算法能力不行，所以他发了这条推文。）

思路：从图上看是要把每棵树的左右子树互换，所以可以用递归快速解决问题。对于任意一个结点，先将其左子树调用当前函数完成翻转，再将其右子树调用当前函数完成翻转。然后交换左右子树，返回这个结点即可。递归的终点是判断给的结点值是否为空，如果为空说明到达叶结点的子树了，直接返回空就行了。代码中可写的稍微简练些，先记录左子树，然后让右子树完成翻转后赋给左子树，左子树完成翻转后赋给右子树。Python中可直接两个变量一起赋值，无需记录。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* invertTree(struct TreeNode* root) {
    if (root == NULL) return NULL;
    struct TreeNode* left = root->left;
    root->left = invertTree(root->right);
    root->right = invertTree(left);
    return root;
}

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root == None: return None
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root