226.反转二叉树

一、题目描述

翻转一棵二叉树。

示例:

输入:

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

输出:

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

备注:
这个问题是受到 Max Howell 原问题 启发的 :

谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板上写出翻转二叉树这道题,这太糟糕了。

二、题解

1.递归

  1. 声明一个辅助指针用于交换当前节点的左右孩子
  2. 递归反转左右孩子的孩子节点

2.代码

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