(PAT 1102) Invert a Binary Tree(反转二叉树+寻找二叉树的根结点)

冷不防 2022-04-23 03:54 159阅读 0赞

The following is from Max Howell @twitter:

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.

Now it's your turn to prove that YOU CAN invert a binary tree!

### Input Specification: ###

Each input file contains one test case. For each case, the first line gives a positive integer N (≤10) which is the total number of nodes in the tree -- and hence the nodes are numbered from 0 to N−1. Then N lines follow, each corresponds to a node from 0 to N−1, and gives the indices of the left and right children of the node. If the child does not exist, a `-` will be put at the position. Any pair of children are separated by a space.

### Output Specification: ###

For each test case, print in the first line the level-order, and then in the second line the in-order traversal sequences of the inverted tree. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.

### Sample Input: ###

8
    1 -
    - -
    0 -
    2 7
    - -
    - -
    5 -
    4 6

### Sample Output: ###

3 7 2 6 4 0 5 1
    6 5 7 4 3 2 0 1

解题思路:

利用前序遍历,遍历到每一个结点时,交换该结点的左右子树即可

void invertBinaryTree(int root) {
    	if (root == -1) return;
    	swap(BTree[root].lchild, BTree[root].rchild);
    	invertBinaryTree(BTree[root].lchild);
    	invertBinaryTree(BTree[root].rchild);
    }

这里的坑点是怎样寻找二叉树的根结点: 根据性质,**二叉树根节点是只有出度没有入度的**,所以在插入节点时,给每个子节点上一个不是根节点的标记,最后没有被上标记的那个就是根节点

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <queue>
    using namespace std;
    const int MAXN = 100001;
    int N;
    struct sNode {
    	int lchild = -1, rchild = -1;
    	bool notRoot = false;
    }BTree[MAXN];
    void invertBinaryTree(int root) {
    	if (root == -1) return;
    	swap(BTree[root].lchild, BTree[root].rchild);
    	invertBinaryTree(BTree[root].lchild);
    	invertBinaryTree(BTree[root].rchild);
    }
    int num1 = 0;
    void inorder(int root) {
    	if (BTree[root].lchild != -1) {
    		inorder(BTree[root].lchild);
    	}
    	cout << root;
    	num1++;
    	if (num1 < N) cout << " ";
    	if (BTree[root].rchild != -1) {
    		inorder(BTree[root].rchild);
    	}
    }
    int num2 = 0;
    void LayerOrder(int root) {
    	queue<int> BFS_QUeue;
    	BFS_QUeue.push(root);
    	while (!BFS_QUeue.empty()) {
    		cout << BFS_QUeue.front();
    		int curnode = BFS_QUeue.front();
    		num2++;
    		if (num2 < N) cout << " ";
    		BFS_QUeue.pop();
    		if (BTree[curnode].lchild != -1) {
    			BFS_QUeue.push(BTree[curnode].lchild);
    		}
    		if (BTree[curnode].rchild != -1) {
    			BFS_QUeue.push(BTree[curnode].rchild);
    		}
    	}
    }
    
    int main() {
    	scanf("%d", &N);
    	for (int i = 0; i < N; ++i) {
    		char lc, rc;
    		scanf("%*c%c %c", &lc, &rc);
    		if (lc == '-' && rc == '-') {
    			BTree[i].lchild = -1;
    			BTree[i].rchild = -1;
    			BTree[BTree[i].lchild].notRoot = true;
    			BTree[BTree[i].rchild].notRoot = true;
    
    		}
        	else if (lc == '-' || rc == '-') {
    			if (lc == '-') {
    				BTree[i].lchild = -1;
    				BTree[i].rchild = rc - '0';
    				BTree[BTree[i].rchild].notRoot = true;
    			}
    			else if(rc == '-'){
    				BTree[i].lchild = lc - '0';
    				BTree[i].rchild = -1;
    				BTree[BTree[i].lchild].notRoot = true;
    			}
    		}
    		else {
    			BTree[i].lchild = lc - '0';
    			BTree[i].rchild = rc - '0';
    			BTree[BTree[i].lchild].notRoot = true;
    			BTree[BTree[i].rchild].notRoot = true;
    		}
    	}
    	//确立根结点
    	int droot = 0;
    	for (int i = 0; i < N; ++i) {
    		if (BTree[i].notRoot == false) {
    			droot = i;
    			break;
    		}
    	}
    	//反转二叉树
    	invertBinaryTree(droot);
    	LayerOrder(droot);
    	cout << endl;
    	inorder(droot);
    	system("PAUSE");
    	return 0;
    }