[LeetCode]226.Invert Binary Tree | 翻转二叉树

题目来源：LeetCode: 226. Invert Binary Tree
趣闻: 据说homebrew的作者Max Howell去Google面试，被要求在白板上手写出二叉树翻转的代码，由于没有写出来被鄙视了。后经Twitter传为笑谈。
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.

Invert a binary tree.
4
/ \
2 7
/ \ / \
1 3 6 9

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

思路

  • 二叉树，递归调用，翻转操作为左右子节点交换位置。时间复杂度O(n)

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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){
        struct TreeNode* tmp;
        tmp = root->left;
        root->left = root->right;
        root->right = tmp;
        if(root->left)
            invertTree(root->left);
        if(root->right)
            invertTree(root->right);
    }
    return root;
    
}

运行结果：

68 / 68 test cases passed.
Status: Accepted
Runtime: 0 ms
Submitted: 0 minutes ago

You are here! Your runtime beats 0.76% of csubmissions.

PS: I have no idea why 0ms only beats 0.76% of submissions!?

总结

  1. 熟悉和理解C的指针操作是该题优势。
  2. 增加子节点NULL判断，减少非必要的循环操作。
  3. 掌握二叉树的操作特点，白板写出也是可以做到的。