[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. 掌握二叉树的操作特点,白板写出也是可以做到的。