?
Invert a binary tree.
4
/ \
2 7
/ \ / \
1 3 6 9 to
4
/ \
7 2
/ \ / \
9 6 3 1
解题思路：类似于后序遍历的思想，递归的思想，先完成左子树的交换，再完成右子树的交换，再将根节点的左右子树交换。
?
未优化代码如下：
?
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root==NULL) return NULL;//当树为一颗空树的时候。
if(root->left||root->right){//当节点的左右子树至少有一个不为空的时候，必须递归进行交换。
TreeNode *node=invertTree(root->left);
root->left=invertTree(root->right);
root->right=node;
return root;
}else{//当该节点左右子树都为空的时候，没有必要交换，直接返回该节点。
return root;
}
}
};
?
之后观看代码可以发现，if-else语句中都有return root;区别在于if语句中对左右子树进行了交换，而else语句中由于左右子树都为空，没有进行交换。
这里，我们可以优化，认为else语句中两棵空子树也进行了交换，这样就可以将if-else语句合并。
优化代码如下：
?
TreeNode* invertTree_recursive(TreeNode* root) {
if (root==NULL) return root;
TreeNode* node = invertTree_recursive(root->left);
root->left = invertTree_recursive(root->right);
root->right = node;
return root;
}
?
?
?
?
版权声明：本文为博主原创文章，未经博主允许不得转载。