翻转二叉树
问题：
思路：
1.层次遍历（迭代）
利用队列遍历，利用STL中的Swap函数将出队的树节点的指向左右子树根节点的指针交换，并将指向左右子树根节点的指针入队
遍历开始前将根节点入队，遍历结束条件为队列为空
2.分治递归
将一颗树翻转，即将其左右子树交换，再将左右子树翻转
当树为空时，递归函数直接返回
代码：
层次遍历（迭代）：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if( root==NULL )
return root;
queue<TreeNode*> q;
TreeNode* p;
q.push( root );
while( q.size()!=0 )
{
p=q.front();
q.pop();
swap( p->left,p->right );
if( p->left!=NULL )
q.push( p->left );
if( p->right!=NULL )
q.push( p->right );
}
return root;
}
};
分治递归：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
change( root );
return root;
}
void change( TreeNode* p )
{
if( p==NULL )
return;
swap( p->left,p->right );
change( p->left );
change( p->right );
}
};
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/153868.html
