L2-035 完全二叉树的层序遍历

分析 根据后序遍历直接创建层次遍历

参考大佬的题解，不太明白

import java.util.Scanner;

public class Main {
    static int n, cnt = 1;
    static int[] a = new int[35];
    static int[] ans = new int[35];

    static void dfs(int u) {
        if (u > n)
            return;
        dfs(2 * u);
        dfs(2 * u + 1);
        ans[u] = a[cnt++];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
        }
        dfs(1);
        for (int i = 1; i <= n; i++) {
            if (i != 1)
                System.out.print(" ");
            System.out.print(ans[i]);
        }
    }
}

建树

1. 在创建新结点，不去引用的话，需要new一下；
2. 此题说了一个条件，是完全二叉树，那么完全二叉树的特点就是当父亲结点编号为i，那么左孩子结点的编号就是2i，右孩子的编号就为2i+1;
3. 后序序列，最后一个结点为根节点，然后后序遍历为：左、右、根；那么假设根结点的索引为k，那k-1，就是根节点的右孩子，然后以右孩子为根节点，递归去建树；当编号超过结点的总数就是递归出口，然后在右子树和左子树的递归后面返回根节点root；
4. 树构造好，层次遍历可见：https://blog.csdn.net/weixin_51995229/article/details/124197521?spm=1001.2014.3001.5502

#include 
using namespace std;

struct Node {
	Node *l;
	Node *r;
	int data;
};
int n, k;
int a[35];
Node *buildTree(int id) { //id:编号
	if (id > n)
		return NULL;
	Node *root = new Node;
	root->data = a[k];//最后一个点为根节点
	k--;
	//先创建右子树，右子树的根节点就是当前根结点的右孩子，也就是k-1的位置的值
	root->r = buildTree(2 * id + 1);//右节点
	root->l = buildTree(2 * id);//左节点
	return root;
}
void levelOrder(Node *root) {
	queue<Node*> q;
	int f = 0;
	if (root != NULL)
		q.push(root);
	while (!q.empty()) {
		if (f == 0)
			cout << q.front()->data;
		else
			cout << " " << q.front()->data;
		f++;
		if (q.front()->l )
			q.push(q.front()->l);
		if (q.front()->r)
			q.push(q.front()->r);
		q.pop();
	}
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	k = n - 1;
	Node *root = buildTree(1);
	levelOrder(root);
	return 0;
}