本文共 712 字,大约阅读时间需要 2 分钟。
非递归算法:
1、交换根节点的左右子节点
2、交换第二层每个节点的左右子节点
....
这个与二叉树层次遍历类似,代码如下:
- TreeNode* invertTree2(TreeNode* root) {
- queue<TreeNode*> tree_queue;
- if (root == NULL)
- return root;
- tree_queue.push(root);
- while(tree_queue.size() > 0){
- TreeNode * pNode = tree_queue.front();
- tree_queue.pop();
- TreeNode * pLeft = pNode->left;
- pNode->left = pNode->right;
- pNode->right = pLeft;
- if (pNode->left)
- tree_queue.push(pNode->left);
- if (pNode->right)
- tree_queue.push(pNode->right);
- }
- return root;
- }
递归算法:
1、交换根节点的左右子树。
2、对左右子树分别执行递归反转 。
代码如下:
- TreeNode* invertTree(TreeNode* root) {
- f(root==NULL)
- return NULL;
- TreeNode * ptmpNode = root->left;
- root->left = invertTree(root->right);
- root->right = invertTree(ptmpNode);
- return root;
- }
转载地址:http://zcrgi.baihongyu.com/