Description

Invert a binary tree.

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

to

1
2
3
4
5
     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.

 

Solution

此题关键在于：递归函数中是应该交换两个指针指向的节点中的存值还是交换两个指针的指向？

如果是交换存值，以Description中的二叉树为例，首轮将2与7的值交换，此时值位7的节点的left指针指向不变，其下层是1和3，程序将继续交换1和3的值。最终产生的结果为：

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

但这是错误的，因此应当交换指针的指向。

 

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    void invert(TreeNode* p)
    {
        if(p == NULL) return;
        TreeNode *temp = p->left;
        p->left = p->right;
        p->right = temp;
        invert(p->left);
        invert(p->right);
    }
    TreeNode* invertTree(TreeNode* root)
    {
        invert(root);
        return root;
    }
};