PAT甲级1102 Invert a Binary Tree：[C++题解]反转二叉树、递归

本文主要是介绍PAT甲级1102 Invert a Binary Tree：[C++题解]反转二叉树、递归，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 题目分析
- 题目链接

题目分析

在这里插入图片描述

反转二叉树这道题目特别出名!!!，是因为Homebrew这款Mac上大火的软件的作者到google面试，就考了这道题。面试官说了下面这段话：你竟然连在白板上翻转二叉树都不会，还是滚吧。

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.

Homebrew简介
在这里插入图片描述
来源：维基百科

分析：反转二叉树，这里用的递归的写法，交换根结点的左右子树。

先交换再遍历左右子树可以；

void dfs_reverse(int u){if(u == -1) return; //没有儿子返回swap(l[u],r[u]);  //交换左右子树   dfs_reverse(l[u]);   dfs_reverse(r[u]);    
}

先遍历左右子树，再交换左右子树也可以。

void dfs_reverse(int u){if(u == -1) return;dfs_reverse(l[u]);    dfs_reverse(r[u]);swap(l[u],r[u]);  //交换左右子树}

ac代码

#include<bits/stdc++.h>
using namespace std;const int N = 20;int l[N] ,r[N];
int q[N];  //数组模拟队列
int n,root;bool has_father[N]; //看当前结点有无父节点，从而求根结点//翻转二叉树
void dfs_reverse(int u){if(u == -1) return;dfs_reverse(l[u]);dfs_reverse(r[u]);swap(l[u],r[u]);  //交换左右子树}//层次遍历bfs
void bfs(int u){int hh = 0 ,tt = 0;q[0] =u;while(hh<= tt){int t =q[hh++];if(l[t] != -1)  q[++tt] = l[t];if(r[t] != -1 ) q[++ tt] = r[t];}cout<< q[0];for(int i=1;i<n;i ++) cout<<" "<<q[i];cout<<endl;
}//中序遍历
/*k用来统计输出的个数，防止行末空格*/
void dfs( int u, int& k){//中序遍历if(u == -1) return;dfs(l[u], k);cout<< u;if(++k !=n) cout<<" ";dfs(r[u] , k);}int main(){//左右儿子数组初始化为-1，表示没有儿子memset(l,-1, sizeof l);memset(r ,-1, sizeof r);cin>> n;for(int i=0; i<n; i++) {char lc, rc;cin>> lc >> rc;if(lc != '-') l[i] = lc -'0',has_father[l[i]] =true;if(rc != '-') r[i] =rc - '0',has_father[r[i]] =true;}root =0;while(has_father[root]) root++;dfs_reverse(root);  //反转二叉树bfs(root); //层次遍历int k =0; //防止行末空格dfs(root , k); //中序遍历
}